链接：https://nanti.jisuanke.com/t/16876
题意：给定一个无向图，求是否含3个或以上有根树，且根在同一个环上。
分析：只含一个环，剩下的都是树，因此必然有n==m，满足这一条件后，找环，环的大小不小于3即满足条件。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=105; 6 int G[maxn][maxn]; 7 int p[maxn],n,m,c[maxn]; 8 int Find(int x){return p[x]==x?x:p[x]=Find(p[x]);} 9 int main(){ 10 int x,y; 11 memset(G,0,sizeof(G)); 12 memset(c,0,sizeof(c)); 13 scanf("%d%d",&n,&m); 14 for(int i=1;i<=n;i++)p[i]=i; 15 for(int i=0;i<m;i++){ 16 scanf("%d%d",&x,&y); 17 G[x][y]=1;G[y][x]=1; 18 c[x]++;c[y]++; 19 int s=Find(x),t=Find(y); 20 if(s!=t){ 21 p[s]=t; 22 } 23 } 24 if(m!=n){ 25 cout<<"SAD"<<endl;return 0; 26 } 27 for(int i=1;i<=n;i++){ 28 if(Find(i)!=Find(1)){ 29 cout<<"SAD"<<endl;return 0; 30 } 31 } 32 while(1){ 33 bool ok=true; 34 for(int i=1;i>=n;i++){ 35 if(c[i]==0)continue; 36 if(c[i]==1){ 37 for(int j=1;j<=n;j++){ 38 c[j]-=G[i][j]; 39 G[j][i]=G[i][j]=0; 40 } 41 c[i]=0; 42 ok=false; 43 break; 44 } 45 } 46 if(ok)break; 47 } 48 int coun=0; 49 for(int i=1;i<=n;i++)if(c[i])coun++; 50 if(coun>=3)cout<<"HAPPY"<<endl; 51 else cout<<"SAD"<<endl; 52 return 0; 53 }