题意：给你2个图，最大度为2.问两个图是否相似。
思路：图中有环、有链，判断环的个数以及每个环组成的人数，还有链的个数以及每个链组成的人数 是否相等即可。
如果形成了环，那么每形成一个环，结点数就会多增加1，如果没形成环，那么结点数就会是一样，根据这里，引入set来写，会轻松很多。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
int father[100000],p[100000],sum[100000];
int find(int x)
{
int i=x,root;
while(x!=father[x])
x=father[x];
root=x;
x=i;
while(x!=father[x])
{
i=father[x];
father[x]=root;
sum[root]=sum[root]+sum[x];
p[root]=p[root]+p[x];
sum[x]=0;
p[x]=0;
x=i;
}
return root;
}
void liantong(int x,int y)
{
if(x!=y)
{
father[x]=y;
sum[y]+=sum[x];
p[y]+=p[x];
sum[x]=0;
p[x]=0;
}
else
{
p[x]++;
}
}
int main()
{
int text,f=1;
scanf("%d",&text);
while(text--)
{
set<int>cir,li;
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
father[i]=i;
p[i]=1;
sum[i]=1;
}
for(int i=1;i<=m;i++)
{
int tmp,tmp1;
scanf("%d%d",&tmp,&tmp1);
if(tmp==tmp1) continue;
tmp=find(tmp);
tmp1=find(tmp1);
liantong(tmp,tmp1);
}
for(int i=1;i<=n;i++)
{
if(p[i]==sum[i])
{
li.insert(p[i]);
}
else
{
cir.insert(p[i]);
}
}
int ans1=li.size(),ans2=cir.size();
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
father[i]=i;
p[i]=1;
sum[i]=1;
}
for(int i=1;i<=m;i++)
{
int tmp,tmp1;
scanf("%d%d",&tmp,&tmp1);
if(tmp==tmp1) continue;
tmp=find(tmp);
tmp1=find(tmp1);
liantong(tmp,tmp1);
}
for(int i=1;i<=n;i++)
{
if(p[i]==sum[i])
{
li.insert(p[i]);
}
else
{
cir.insert(p[i]);
}
}
//printf("%d %d\n%d %d\n",ans1,ans2,cir.size(),li.size()); if(cir.size()==ans2&&li.size()==ans1)
printf("Case #%d: YES\n",f++);
else
printf("Case #%d: NO\n",f++);
}
return 0;
}