题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3926
题意：给定2个顶点度最大为2的无向图。问你这2个无向图是否同构。
思路：
1.最大度为2.说明这个图可能有多个连通分量，每个连通分量要么是环，要么是链。
2.然后遍历每个连通分量，记录该连通分量的结点个数，以及该连通分量是环还是链。
3.将第一个图按照结点个数排序（若子结点个数相同，则对链先排序）
4.将第二个图按照步骤三排序
5.比较排序后，2个图是否每个元素都相等。若相等，则相似。
关于求链通分量，当然是并查集的一些基本操作了，不过合并的时候应该遵循孩子节点少的合并到孩子节点多的集合中(不然wa),然后就是排序后比较一下就可以了（因为图可能存在环，因此可以先按孩子节点的个数排，然后再按是否存在环排）
#include<time.h>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=+;
int na,ma,nb,mb,t,Ca=,FaA[MAXN],FaB[MAXN];
struct Node{
int cnt; //连通分量的点数
int Type; //1：是环 0：链
Node(int a=,int b=):cnt(a),Type(b){};
}GroupA[MAXN],GroupB[MAXN]; //图1，图2
void Init(){ //初始化
for(int i=;i<MAXN;i++){
FaA[i]=i; FaB[i]=i;
GroupA[i].cnt=; GroupA[i].Type=;
GroupB[i].cnt=; GroupB[i].Type=;
}
}
int Find(int x,int *Fa){ //并查集
return x==Fa[x]?x:Fa[x]=Find(Fa[x],Fa);
}
void Union(int x,int y,int *Fa,Node *Group){//并查集
int rootx=Find(x,Fa);
int rooty=Find(y,Fa);
if(rootx==rooty){ //存在环
Group[rootx].Type=;
}
else{ //把小的合并到大的树上
if(Group[rootx].cnt>=Group[rooty].cnt){
Group[rootx].cnt+=Group[rooty].cnt;
Fa[rooty]=rootx;
}
else{
Group[rooty].cnt+=Group[rootx].cnt;
Fa[rootx]=rooty;
}
}
}
bool cmp(Node a,Node b){ //排序函数，先按点数排，点数相同则优先排链再到环
if(a.cnt!=b.cnt){
return a.cnt<b.cnt;
}
return a.Type<b.Type;
}
bool solve(){ //比较2个图是否同构
sort(GroupA,GroupA+na+,cmp);
sort(GroupB,GroupB+nb+,cmp);
for(int i=;i<=na;i++){
if((GroupA[i].Type!=GroupB[i].Type)||(GroupA[i].cnt!=GroupB[i].cnt)){
return false;
}
}
return true;
}
int main()
{
scanf("%d",&t);
while(t--){
Init();
scanf("%d %d",&na,&ma);
for(int i=;i<=ma;i++){
int u,v;
scanf("%d%d",&u,&v);
Union(u,v,FaA,GroupA);
}
scanf("%d %d",&nb,&mb);
for(int i=;i<=mb;i++){
int u,v;
scanf("%d %d",&u,&v);
Union(u,v,FaB,GroupB);
}
printf("Case #%d: ",Ca++);
if((na!=nb)||(ma!=mb)){ //点数/边数不匹配
printf("NO\n");
continue;
}
if(solve()){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return ;
}