题意：给出两图，判断是否是同构图。
题解：判断给出的链和环，若果是链，则判断链里边时候是同构，排序。如果是环，则判断环里边的个数。
要判断每个点，把每条边加入到并查集中去，记录是环或者链。每次并查集加入的时候，链或者环的长度会变化，所以要改变链的长度。
#include <stdio.h> #include <algorithm> #include <math.h> #include <string.h> #include <vector> #include <queue> #include <map> #include <stack> #include <iostream> #define pi acos(-1.0) #define INF 0x3f3f3f3f using namespace std; #define ll long long const int maxn=50010; struct node { int num; int cl; bool operator < (const node &tmp) const { if(tmp.num==num) return tmp.cl<cl; return tmp.num<num; } }nd1[maxn],nd2[maxn]; int f[maxn]; int found(int x) { if(x!=f[x]) f[x]=found(f[x]); return f[x]; } int main() { // freopen("C:\Users\Administrator\Desktop\a.txt","r",stdin); //ios::sync_with_stdio(false); //freopen("C:\Users\Administrator\Desktop\b.txt","w",stdout); int n1,n2,m1,m2,T,Case=0; scanf("%d",&T); while(T--) { bool flag=true; scanf("%d%d",&n1,&m1); for(int i=0;i<=maxn;i++) { nd1[i].num=1,nd1[i].cl=0; nd2[i].num=1,nd2[i].cl=0; } for(int i=0;i<=n1;i++) f[i]=i; for(int i=0;i<m1;i++) { int a,b; scanf("%d%d",&a,&b); int fx=found(a),fy=found(b); if(fx!=fy) { f[fx]=fy; nd1[fy].num+=nd1[fx].num; nd1[fx].num=0; } else nd1[fy].cl=1; } scanf("%d%d",&n2,&m2); if(n1!=n2||m1!=m2) flag=false; for(int i=0;i<=n2;i++) f[i]=i; for(int i=0;i<m2;i++) { int a,b; scanf("%d%d",&a,&b); int fx=found(a),fy=found(b); if(fx!=fy) { f[fx]=fy; nd2[fy].num+=nd2[fx].num; //改变链的长度，合并完后也要改变 nd2[fx].num=0; } else nd2[fy].cl=1; } sort(nd1+1,nd1+n1+1); sort(nd2+1,nd2+n2+1); for(int i=1;i<=n1;i++) { if(nd1[i].num!=nd2[i].num||nd1[i].cl!=nd2[i].cl) { flag=false; break; } } if(!flag) printf("Case #%d: NO ",++Case); else printf("Case #%d: YES ",++Case); } return 0; }