首页 > POJ解题报告 > POJ 1161 The Suspects[并查集]

POJ 1161 The Suspects[并查集]

并查集分三个操作,并、查、初始化。初始化时把秩初始化为0,值和父亲都是自己;查的时候看看节点的父亲是不是自己,如果是,则停止查找,如果不是,查找父节点的父节点,同时压缩路径,把子孙节点的父节点都更新为最后找到的父节点。并的时候判断下两个节点是不是在一个集合中,如果不在,判断两个节点的父节点的秩,秩大的做父节点。如果秩相等,则任意一个节点作为父节点,作为父节点的秩增加1.
传送题目地址:POJ 1161 The Suspects http://poj.org/problem?id=1611

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
 
typedef struct _S_NODE
{
	int rank;
	int parent;
	int value;
} Node;
 
#define MAX_NUM (30000 + 10)
 
Node node[MAX_NUM];
 
void Init(int n)
{
	int i;
	for (i = 0; i < n; ++i)
	{
		node[i].rank = 0;
		node[i].value = node[i].parent = i;
	}
}
 
int Find(int x)
{
	if (x != node[x].parent)
	{
		node[x].parent = Find(node[x].parent);
	}
	return node[x].parent;
}
 
void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
 
	if (x != y)
	{
		if (node[x].rank > node[y].rank)
		{
			node[y].parent = x;
		}
		else
		{
			node[x].parent = y;
			if (node[x].rank == node[y].rank)
			{
				++node[y].rank;
			}
		}
	}
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int n, m, i, j;
	while (scanf ("%d %d", &n, &m))
	{
		if (!m && !n) break;
		Init(n);
		for (i = 0; i < m; ++i)
		{
			int k, tmp, t;
			scanf ("%d", &k);
			if (!k) continue;
			scanf ("%d", &tmp);
			for (j = 1; j < k; ++j)
			{
				scanf ("%d", &t);
				Union(tmp, t);
			}
		}
		int res = 0;
		for (i = 0; i < n; ++i)
		{
			if (Find(0) == Find(i))
			{
				++res;
			}
		}
		printf ("%d\n", res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 1161 The Suspects[并查集]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2011年9月15日11:46 | #1

    继续学习 [em022]

    [回复]

    代码疯子 回复:

    @代码部落(Winson), 呵呵互相学习

    [回复]