本文共 1760 字，大约阅读时间需要 5 分钟。
这个题和小希的迷宫很相似但是差一些 有向图和无向图
因为如果是一棵树 根只能有一个 因为是有向图 根肯定是最上面的 它的入度是0 这样的点只能有一个
不能有环
#include #include #include #include using namespace std;int fa[100050];int vis[100050];int ru[100050];int chu[100050];bool ok;void init(){ for(int i=0;i<100040;i++) { fa[i]=i; vis[i]=0; ru[i]=0; chu[i]=0; } ok=true;}int find(int i){ return fa[i]==i?i:find(fa[i]);}void un(int a,int b){ int aa=find(a); int bb=find(b); if(aa==bb) ok=false; else fa[aa]=bb; return ;}int main(){ int t=0; int a,b; while(~scanf("%d%d",&a,&b)) { if(a<0&&b<0) break; t++; init(); if(a==0&&b==0) printf("Case %d is a tree.\n",t); else { un(a,b); vis[a]=1; vis[b]=1; chu[a]++; ru[b]++; while(~scanf("%d%d",&a,&b)) { if(a==0&&b==0) break; un(a,b); vis[a]=1; vis[b]=1; chu[a]++; ru[b]++; } int ma=0; int yi=0; int er=0; for(int i=0;i<100040;i++) { if(vis[i]==1) { if(fa[i]==i) { ma++; } if(ru[i]==0) { yi++; } } } if(ma==1&&yi==1&&ok==true) printf("Case %d is a tree.\n",t); else printf("Case %d is not a tree.\n",t); } }}
转载于:https://www.cnblogs.com/rayrayrainrain/p/5189837.html