这个题也太🐕了
0 0空集是树(没好好读题)
有环不是树(没想到)
其他并查集判断是否是一个连通图,如果是的话且没环就是树
#include<iostream> #include<map> #include<vector> using namespace std; const int maxn=10001; int father[maxn]; int height[maxn]; int indegree[maxn]; bool flag=false; map<int,int> mp;//记录点有没有出现过 int index=0; void init(){ for(int i=0;i<maxn;i++){ father[i]=-1; height[i]=0; indegree[i]=-1; mp.clear(); flag=false; } } int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; } void Union(int x,int y){ x=find(x); y=find(y); if(x!=y){ if(height[x]>height[y]) father[y]=x; else if(height[y]>height[x]) father[x]=y; else{ father[x]=y; height[y]++; } } } void test(){ int root=0; int sum=0; for(int i=0;i<maxn;i++){ if(father[i]==i) sum++; if(indegree[i]==0) root++; if(indegree[i]>=2 || sum>=2){ flag=true; } } if(sum!=0&&root==0)flag=true; if(flag) printf("Case %d is not a tree.\n",index); else printf("Case %d is a tree.\n",index); } int main(){ int i,j; init(); while(cin>>i>>j){ if(i==0&&j==0){ index++; test(); init(); } else if(i==-1&&j==-1){ break; } else{ if(mp.find(i)==mp.end()){ mp[i]=1; father[i]=i; indegree[i]=0; } if(mp.find(j)==mp.end()){ mp[j]=1; father[j]=j; indegree[j]=0; } Union(i,j); if(i==j)flag=true; indegree[j]++; } } return 0; }