Description
Input
Output
Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Sample Output
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int maxn=100005; int father[maxn]; bool vis[maxn]; void init(){ for(int i=0;i<maxn;i++){ father[i]=i; vis[i]=false; } } int get_father(int x){ if(father[x]!=x) father[x]=get_father(father[x]); return father[x]; } int main(){ int u,v; bool flag=true; init(); while(scanf("%d%d",&u,&v)!=EOF){ if(u==-1&&v==-1) break; if(u==0&&v==0){ printf("Yes\n"); continue; } vis[u]=true; vis[v]=true; father[u]=v; while(scanf("%d%d",&u,&v)!=EOF){ if(u==0&&v==0) break; vis[u]=true; vis[v]=true; int t1=get_father(u); int t2=get_father(v); if(t1!=t2) father[t1]=t2; else flag=false; } int ans; for(int i=0;i<maxn;i++){ if(vis[i]){ ans=get_father(i); break; } } for(int i=0;i<maxn;i++){ if(vis[i]){ if(get_father(i)!=ans){ flag=false; break; } } } if(flag) printf("Yes\n"); else printf("No\n"); flag=true; init(); } return 0; }
Description
Input
Output
Sample Input
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Sample Output
Case 1 is a tree. Case 2 is a tree. Case 3 is not a tree.
本题和上题几乎一样，只不过这道题判断的时不时一个树。
这里我们需要注意三点
1本题给的虽然是有向图，但是并不影响树的构建，当成无向图就可以了，用并查集合并的时候，代码和上道题是一模一样的
2如果输入的数据只有一组，那么一个点是孤立的节点，他是构不成一个树的
3如果只是输入0 0 ，那么这是一个空树，但是也是一个树，所以我们仍需要默认其为一个树
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int maxn=100005; int father[maxn]; bool vis[maxn]; void init(){ for(int i=0;i<maxn;i++){ father[i]=i; vis[i]=false; } } int get_father(int x){ if(father[x]!=x) father[x]=get_father(father[x]); return father[x]; } int main(){ int u,v; bool flag=true; init(); int cnt=1; while(scanf("%d%d",&u,&v)!=EOF){ if(u==-1&&v==-1) break; if(u==0&&v==0){ printf("Case %d is a tree.\n",cnt++); continue; } vis[u]=true; vis[v]=true; father[u]=v; while(scanf("%d%d",&u,&v)!=EOF){ if(u==0&&v==0) break; vis[u]=true; vis[v]=true; int t1=get_father(u); int t2=get_father(v); if(t1!=t2) father[t1]=t2; else flag=false; } int ans; int sum=0; for(int i=0;i<maxn;i++){ if(vis[i]){ ans=get_father(i); break; } } for(int i=0;i<maxn;i++){ if(vis[i]){ sum++; if(get_father(i)!=ans){ flag=false; break; } } } if(flag&&sum!=1) printf("Case %d is a tree.\n",cnt++); else printf("Case %d is not a tree.\n",cnt++); flag=true; init(); } return 0; }
原文：http://www.cnblogs.com/13224ACMer/p/5013791.html