思路如题。
但坑点是:
#会出现0,0这样单组的数据,并且要求你输出yes----这个没有那位兄弟的提醒我是想不到的
#题目看似要求你判断是否为树,实际上除了flag==0以外,还得联通。
第一次wa在0,0,第二次wa在没有判断联通。第三次wa在处理第一次的wa时,用了一个continue,下面的ok就没有++;
#include <iostream> #include <math.h> #include <string.h> #include <vector> #include <map> #include <queue> #include <stdio.h> #include <algorithm> #include <cstdio> using namespace std; const int maxn=1e6+5; int flag=0,cnt=0,vis[maxn],fa[maxn]; int find(int x) { if(fa[x]!=x) { fa[x]=find(fa[x]); } return fa[x]; } void unit(int x,int y) { int f1=find(x),f2=find(y); if(f1==f2) { flag=1; return; } else { fa[f2]=f1; } } void pre( ) { for(int i=1;i<=maxn;i++) { vis[i]=0; fa[i]=i; } flag=0; cnt=0; } int main() { freopen("lys.in","r",stdin); int a,b,ok=1; pre(); while(ok) { cin>>a>>b; if(a==-1) { ok=0;break; } if(a!=0) { cnt++; unit(a,b); vis[a]=1; vis[b]=1; } else if(a==0) { if(cnt==0) { printf("Case %d is a tree.\n",ok); ok++; continue; } if(flag==1) { printf("Case %d is not a tree.\n",ok); } else { int f=0; for(int i=1;i<=maxn;i++) { if(vis[i]==0) { continue; } if(f==0) { f=find(i); } else { if(f!=find(i)) { flag=1; } } } if(flag==1) { printf("Case %d is not a tree.\n",ok); } else { printf("Case %d is a tree.\n",ok); } } pre( ); ok++; } } }