连通图
吉林大学机试题目
本来以为n<=1000,使用floyd算法会超时,没想到通过了。
#include<bits/stdc++.h>
using namespace std;
#define maxn 1005
int edge[maxn][maxn];
int main(){
int n,m,a,b;
while(scanf("%d %d",&n,&m)!=EOF){
memset(edge,-1,sizeof(edge));
for(int i=1;i<=n;i++) edge[i][i] = 0;
while(m--){
scanf("%d %d",&a,&b);
edge[a][b] = 1;
edge[b][a] = 1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(edge[i][k]==-1||edge[k][j]==-1) continue;
if(edge[i][j]==-1){
edge[i][j] = edge[i][k]+edge[k][j];
}
}
}
}
bool flag = false;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(edge[i][j]==-1){
flag = true;
break;
}
}
if(flag==true) break;
}
if(flag==true) printf("NO\n");
else printf("YES\n");
}
return 0;
}