今天又准备刷图论结果又卡在一道题了
  • 板块灌水区
  • 楼主gdjcwsk
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/4/29 21:19
  • 上次更新2023/11/7 03:37:40
查看原帖
今天又准备刷图论结果又卡在一道题了
243024
gdjcwsk楼主2020/4/29 21:19

MLE了两个点

题面是这个:

题目描述

给出一个无向图,请判断其中是否包含重边和自环。

输入格式

第一行包含两个整数N、M,表示该图共有N个结点和M条无向边。(N<=5000,M<=200000)。

接下来M行每行包含三个整数{u,v,w},表示有一条长度为w的无向边连接结点u、v。

输出格式

self-loops?Yes/No

parallel edges?Yes/No

输入输出样例

输入 #1

4 5

1 1 2

1 3 2

1 4 3

2 3 4

3 1 3

输出 #1

self-loops?Yes

parallel edges?Yes

我的代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=5005;
int a[maxn][maxn];
bool f;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        if(u==v)
        {
            f=1;
        }
        a[u][v]++;
        a[v][u]++;
    }
    if(f==1)
    {
        cout<<"self-loops?Yes"<<endl;
    }
    else
    {
        cout<<"self-loops?No"<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]>1)
            {
                cout<<"parallel edges?Yes";
                return 0;
            }
        }
    }
    cout<<"parallel edges?No";
}
2020/4/29 21:19
加载中...