首页 > ACM题库 > HDU-杭电 > HDU 3926-Hand in Hand-并查集-[解题报告]HOJ
2015
04-14

HDU 3926-Hand in Hand-并查集-[解题报告]HOJ

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3926

题目大意:给你2个图,最大度为2.问两个图是否相似

解题思路:

本质是并查集,但是细节是在是恶心死人了。。。

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 link1, link2;
	int hand1, hand2;
	int ans1, ans2;
	bool flag;
	scanf("%d", &ncase);
	while(ncase--)
	{
		flag = true;
		scanf("%d%d", &num1, &link1);
		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);
		}
		scanf("%d%d", &num2, &link2);
		if(link2 != link1) //边数不同跳出
			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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/niushuai666/article/details/6916764


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮