2015
04-14

# Hand in Hand

In order to get rid of Conan, Kaitou KID disguises himself as a teacher in the kindergarten. He knows kids love games and works out a new game called "hand in hand".

Initially kids run on the playground randomly. When Kid says "stop", kids catch others’ hands immediately. One hand can catch any other hand randomly. It’s weird to have more than two hands get together so one hand grabs at most one other hand. After kids stop moving they form a graph.

Everybody takes a look at the graph and repeat the above steps again to form another graph. Now Kid has a question for his kids: "Are the two graph isomorphism?"

The first line contains a single positive integer T( T <= 100 ), indicating the number of datasets.
There are two graphs in each case, for each graph:
first line contains N( 1 <= N <= 10^4 ) and M indicating the number of kids and connections.
the next M lines each have two integers u and v indicating kid u and v are "hand in hand".
You can assume each kid only has two hands.

The first line contains a single positive integer T( T <= 100 ), indicating the number of datasets.
There are two graphs in each case, for each graph:
first line contains N( 1 <= N <= 10^4 ) and M indicating the number of kids and connections.
the next M lines each have two integers u and v indicating kid u and v are "hand in hand".
You can assume each kid only has two hands.

2

3 2
1 2
2 3
3 2
3 2
2 1

3 3
1 2
2 3
3 1
3 1
1 2

Case #1: YES
Case #2: NO

1.最大度为2.说明这个图可能有多个连通分量，每个连通分量要么是环，要么是链。

2.然后遍历每个连通分量，记录该连通分量的结点个数，以及该连通分量是环还是链。

3.将第一个图按照结点个数排序（若子结点个数相同，则对链先排序）

4.将第二个图按照步骤三排序

5.比较排序后，2个图是否每个元素都相等。若相等，则相似。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<climits>
#include<algorithm>
using namespace std;
#define MAXN 10010
int pre1[MAXN], pre2[MAXN]; //父节点
int num1, num2;

struct graph //图的子结点数目，是否为环
{
int son;
bool ring;
};
graph g1[MAXN], g2[MAXN];

bool cmb(const graph &g1, const graph &g2) //子结点优先+先链后环排序
{
if(g1.son < g2.son)
return true;
else if(g1.son == g2.son && g1.ring < g2.ring)
return true;
else
return false;
}

int find(int x, int pre[]) //查找根结点+路径压缩
{
return x == pre[x] ? x : find(pre[x], pre);
}

void join(int x, int y, int pre[],graph g1[]) //合并
{
int root1, root2;
root1 = find(x, pre);
root2 = find(y, pre);
if(root1 == root2)
g1[root1].ring = true; //为环
else
{
if(g1[root1].son >= g1[root2].son) //结点相加
{
pre[root2] = root1;
g1[root1].son += g1[root2].son;
}
else
{
pre[root1] = root2;
g1[root2].son += g1[root1].son;
}
}
}

bool cmp(int num, graph g1[], graph g2[]) //判断图是否同构
{
sort(g1 + 1, g1 + num + 1, cmb); //排序
sort(g2 + 1, g2 + num + 1, cmb);
for(int i = 1; i <= num; ++i)
if(g1[i].son != g2[i].son || (g1[i].son == g2[i].son && g1[i].ring != g2[i].ring))
return false;
return true;
}

int main()
{
int ncase, T = 0;
int hand1, hand2;
int ans1, ans2;
bool flag;
scanf("%d", &ncase);
while(ncase--)
{
flag = true;
for(int i = 1; i < MAXN; ++i) //初始化
{
pre1[i] = i;
pre2[i] = i;
g1[i].son = 1;
g2[i].son = 1;
g1[i].ring = false;
g2[i].ring = false;
}
for(int i = 1; i <= link1; ++i)
{
scanf("%d%d", &hand1, &hand2);
join(hand1, hand2, pre1, g1);
}
flag = false;
for(int i = 1; i <= link2; ++i)
{
scanf("%d%d", &hand1, &hand2);
if(flag == false)
continue;
else
join(hand1, hand2, pre2, g2);
}
flag = cmp(num2, g1, g2);
if(flag == false)
printf("Case #%d: NO\n", ++T);
else
{
if(flag)
printf("Case #%d: YES\n", ++T);
else
printf("Case #%d: NO\n", ++T);
}
}
return 0;
}

1. 其实,我的观点很简单,老百姓或者叫民众,永远都是枪,永远也不会成为握枪的人,而自从老百姓存在,争抢这把枪的斗争就没有停止过. 历史上凡那些代表”"先进”"的人,其实他们的团体可能早就存在,不过是争夺这把枪的幕后势力的提线木偶罢了. 至于战争, 小规模,局部

2. 其实,我的观点很简单,老百姓或者叫民众,永远都是枪,永远也不会成为握枪的人,而自从老百姓存在,争抢这把枪的斗争就没有停止过. 历史上凡那些代表”"先进”"的人,其实他们的团体可能早就存在,不过是争夺这把枪的幕后势力的提线木偶罢了. 至于战争, 小规模,局部

3. 其实,我的观点很简单,老百姓或者叫民众,永远都是枪,永远也不会成为握枪的人,而自从老百姓存在,争抢这把枪的斗争就没有停止过. 历史上凡那些代表”"先进”"的人,其实他们的团体可能早就存在,不过是争夺这把枪的幕后势力的提线木偶罢了. 至于战争, 小规模,局部

4. 其实,我的观点很简单,老百姓或者叫民众,永远都是枪,永远也不会成为握枪的人,而自从老百姓存在,争抢这把枪的斗争就没有停止过. 历史上凡那些代表”"先进”"的人,其实他们的团体可能早就存在,不过是争夺这把枪的幕后势力的提线木偶罢了. 至于战争, 小规模,局部

5. 其实,我的观点很简单,老百姓或者叫民众,永远都是枪,永远也不会成为握枪的人,而自从老百姓存在,争抢这把枪的斗争就没有停止过. 历史上凡那些代表”"先进”"的人,其实他们的团体可能早就存在,不过是争夺这把枪的幕后势力的提线木偶罢了. 至于战争, 小规模,局部

6. 其实,我的观点很简单,老百姓或者叫民众,永远都是枪,永远也不会成为握枪的人,而自从老百姓存在,争抢这把枪的斗争就没有停止过. 历史上凡那些代表”"先进”"的人,其实他们的团体可能早就存在,不过是争夺这把枪的幕后势力的提线木偶罢了. 至于战争, 小规模,局部