HDU 1325 1272 并查集判断有向图和无向图是否构成一棵树型

Posted on | In | Comments:
| 19k | 18 mins.

HDU 1325
HDU 1272

HDU 1325是有向图，给定某个节点是另一个元素的父节点
HDU 1272是无向图，将两个节点连接起来

共同点：判断是否成环，判断是树木还是森林

区别：有向图可能出现多个箭头指向同一个节点的情况（即一个节点多个父节点）
例如
多节点指向同一节点

另外，关于HDU 1272

评论区看到一种利用离散数学结论的解法
（对于无向图）
如果m个节点被连成环，那么边的条数就是 m
如果m个节点形成了n个树，那么边的条数就是 m - n
（这个动动笔画画就能明白）
链接：这题目干嘛都用并查集做啊
那么按照题目要求：Yes的条件就是
1.边的条数 = 所有节点数 - 1
或
2.节点数为0

上代码：
HDU 1325

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define maxlen 200005

using namespace std;

//并查集实现

int roots, ok;

int fa[maxlen];

// 这个栈和栈顶指针只是用来记录出现过的元素，用来清空fa数组用的，
// 记录fa数组的哪些地方被用过了，
// 完成一个示例以后就根据这个栈里面记录的位置来把fa数组里面对应的位置恢复成0
// 之所以不用memset，是因为fa数组很大，不是所有部分都用上了，每次都把整个数组写0太浪费时间了
int stack[maxlen];
int top = -1;

int find(int i) {//非递归实现
	int icopy = i;
	while (i != fa[i]) {//找到根元素
		i = fa[i];
	}

	while (icopy != fa[icopy]) {
		icopy = fa[icopy];//获取父节点
		fa[icopy] = i;//挂到根节点下
	}

	return i;
}

int main(int argc, char const *argv[]) {

	int a, b, t = 1;

	int count = 0;
	while (1) {

		ok = 1;
		count = 0;

		// memset(fa, 0, sizeof(fa));//每次都全部写0，耗时长，改为用栈记录修改过的位置

		while (scanf("%d%d", &a, &b) && a > 0 && b > 0) {

			// a --> b
			// a是b的父节点

			if (ok) {
				if (!fa[a]) { //若a没有出现过,就初始化为自己
					fa[a] = a;
					count++;

					top++;
					stack[top] = a;
					// printf("add\n");
				}
				if (!fa[b]) {
					fa[b] = b;

					top++;
					stack[top] = b;

				} else {
					if (fa[b] == b) {
						count--;
						// printf("sub\n");
					}
				}

				if (fa[b] != b && fa[b] != a) {//若出现多指一,则不ok
					ok = 0;
					// printf("die 1\n");
					continue;
				} else {
					a = find(a);//把a换为a的根节点
					if (b == a) {//环
						ok = 0;
						// printf("die 2\n");
						continue;
					} else {
						fa[b] = a;//直接挂在根节点
					}
				}
			}
		}

		if (a < 0 && b < 0) {
			break;
		}
		if (ok) {
			if (count != 1) {
				ok = 0;
				// printf("die 3\n");
			}
		}

		printf("Case %d is %sa tree.\n", t, ok ? "" : "not ");

		while (top != -1) {
			fa[stack[top]] = 0;
			top--;
		}

		t++;
	}

	return 0;
}

HDU 1272

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define maxlen 200005

using namespace std;

//并查集实现
//虽然给的输入似乎是无向的，但最终我们构造的依然是一个有向的树，我们只要考虑是否会出现环和森林，所以这题和hdu1325性质相同

int ok;

int fa[maxlen];

// 这个栈和栈顶指针只是用来记录出现过的元素，用来清空fa数组用的，
// 记录fa数组的哪些地方被用过了，
// 完成一个示例以后就根据这个栈里面记录的位置来把fa数组里面对应的位置恢复成0
// 之所以不用memset，是因为fa数组很大，不是所有部分都用上了，每次都把整个数组写0太浪费时间了
int stack[maxlen];
int top = -1;

int find(int i) {//非递归实现
	int icopy = i;
	while (i != fa[i]) {//找到根元素
		i = fa[i];
	}

	while (icopy != fa[icopy]) {
		icopy = fa[icopy];//获取父节点
		fa[icopy] = i;//挂到根节点下
	}

	return i;
}

int main(int argc, char const *argv[]) {

	int a, b;

	int countOfRoots = 0;
	while (1) {

		ok = 1;
		countOfRoots = 0;

		// memset(fa, 0, sizeof(fa));//每次都全部写0，耗时长，改为用栈记录修改过的位置

		while (scanf("%d%d", &a, &b) && a > 0 && b > 0) {

			if (ok) {

				if (!fa[a]) { //若a没有出现过,就初始化为自己

					top++;
					stack[top] = a;//所有出现过的节点都记录在stack中

					if (!fa[b]) {//若b也没有出现过

						top++;
						stack[top] = b;

						//指定a为b的父节点,a为独立的根节点

						fa[a] = a;
						fa[b] = a;
						countOfRoots++;//根节点数量+1

					} else {//若b出现过

						fa[a] = find(b);//把a直接挂到b的根节点下

					}

				} else {//若a出现过

					if (!fa[b]) {//而b没出现过

						top++;
						stack[top] = b;

						fa[b] = find(a);//把b直接挂到a的根节点下
					} else {//b也出现过

						if (find(a) == find(b)) {//同一根节点
							//成环
							ok = 0;
						} else {
							// 把两个树合并
							fa[find(a)] = find(b);
							countOfRoots--;
						}
					}
				}
			}
		}

		if (a < 0 && b < 0) {
			break;
		}

		if (ok) {
			if (top != -1) {//排除掉一个元素都没有的情况（空树）
				if (countOfRoots != 1) {
					ok = 0;
				}
			}
		}

		printf("%s\n", ok ? "Yes" : "No");

		while (top != -1) {
			fa[stack[top]] = 0;
			top--;
		}
	}

	return 0;
}