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

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;
}