题目大意是给你两张图，让你判断这两张图是否同构，条件是两张图上的点最多都只有两个度数，可以看作是一个简单的同构图问题。
首先说一下什么是同构图
按字面意思理解，同构图即为"相同结构的图"，用图论中的术语描述就是 >图论当中的术语，假设G=(V,E)和G1=(V1，E1)是两个图，如果存在一个双射(即一一映射)m：V→V1，使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1，则称G和G1是同构的,这样的一个映射m称之为一个同构
而我对于同构图的理解是，一个同构图，应具有相同的连通性，链/环的个数以及链上/环上的点的个数应相同，点与点、边与边之间的对应关系应相同
比方说，下面的就是一对同构图
左图是一个只由五元环组成的图，而右图看起来和左图很不一样，但实际上也是一个五元环，边、点一一对应，故两者同构
回到这道题目上。要判断两个图是否同构，实际上是一个比较复杂的问题。一个比较简单粗暴的方法是比较两个图的邻接矩阵，若经过有限次的行变换和列变换后两个矩阵相同，则两图同构。也有用搜索的方法做的......具体的就不说了。但因为这道题每个点最多只有两个度，所以问题大大简化，故可以使用并查集来做，即用并查集检查两张图上链与环的数量，同时检查链/环上点的数目，比较一下，如果都相等则为同构，否则不同构。
代码如下
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
const int maxn=1e4+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n1,n2,m;
int pre[maxn];
int cnt[maxn];
struct kid{
int rcnt;
int ccnt;
kid():rcnt(0),ccnt(1){}
};
bool cmp(kid node1,kid node2)
{
if(node1.ccnt==node2.ccnt)
return node1.rcnt<node2.rcnt;
return node1.ccnt<node2.ccnt;
}
void init(int n)
{
for(int i=1;i<=n;i++)
pre[i]=i;
}
int findr(int x)
{
if(x==pre[x]) return pre[x];
return pre[x]=findr(pre[x]);
}
int main()
{
int t;
cin>>t;
int kase=0;
while(t--)
{
kid k1[maxn];
kid k2[maxn];
cin>>n1>>m;init(n1);
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
int fu=findr(u);
int fv=findr(v);
if(fu!=fv){
pre[fu]=fv; //将fu接到fv上
k1[fv].ccnt+=k1[fu].ccnt;
k1[fu].ccnt=0;
}else{
k1[fv].rcnt++; //以fv为代表元素的环有多少个元素
}
}
cin>>n2>>m;init(n2);
for(int i=0;i<m;i++){
int u,v;
scanf("%d %d",&u,&v);
int fu=findr(u);
int fv=findr(v);
if(fu!=fv){
pre[fu]=fv;
k2[fv].ccnt+=k2[fu].ccnt;
k2[fu].ccnt=0;
}else{
k2[fv].rcnt++;
}
}
bool flag=1;
if(n1!=n2){
flag=0;
}else{
sort(k1+1,k1+n1+1,cmp);
sort(k2+1,k2+n2+1,cmp);
for(int i=1;i<=n1;i++){
if(k1[i].ccnt!=k2[i].ccnt||k1[i].rcnt!=k2[i].rcnt){
flag=0;
break;
}
}
}
if(flag)
printf("Case #%d: YES\n",++kase);
else
printf("Case #%d: NO\n",++kase);
}
return 0;
}