Contents
Problem
Solution
有幾個比較重要的關係：
- (A, B) 是朋友、(B, C) 是朋友： (A, C) 是朋友
- (A, B) 是敵人、(B, C) 是敵人： (A, C) 是朋友
- (A, B) 是朋友、(B, C) 是敵人： (A, C) 是敵人
要特別注意的是：
setEnemies(A, B) 時，也要將 (A 的敵人) 和 (B) 化為朋友、(B 的敵人) 和 (A) 化為朋友(Union)。
setFriends(A, B) 時，則是也要讓 (A 的敵人) 和 (B 的敵人) 化為朋友(Union)。
第一種作法，讓 A 分成兩部分，分別是 (A) 和 (A’s enemy)。
只要和 p[A] 相同的代表是朋友，和 p[A's enemy] 相同的則是 A 的敵人。
由於分成了兩個不同的數字，就可以直接對他們去做 union 等操作了。
第二種則是額外用一個 enemy[A] 去紀錄 A 的敵人，需要在每一次更動關係時去追蹤 A 的敵人。
在 setFriends 中有個一開始沒寫到，一直拿 WA 的原因…
1 | //兩方的敵人會成為朋友，並更新紀錄敵人的陣列 |
要注意 空集合 的判斷，並記得以各隊(朋友)的代表去操作。
一開始使用第二種，儘管可以過 udebug，還是 WA 了快 20 次才找到問題…
提供一個比較好手算的測資：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
167
1 1 2
1 3 4
2 2 3
1 1 4
2 4 5
2 1 5
1 5 6
3 1 6
3 3 6
0 0 0
-1
-1
1
0
Code
(1)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
//disjoint set
int n;
int p[N]; //the leader of each unit([x]: x 的代表)
int size[N]; //number of each group([x]: x 的成員有幾人)
inline void init()
{
for (int i = 0; i < (n << 1); ++i)
{
size[i] = 1;
p[i] = i;
}
}
inline int find(int x)
{
return (x == p[x]) ? x : (p[x] = find(p[x]));
}
inline int get_ene(int x) //x 的敵人
{
return x + n;
}
inline void do_union(int x, int y)
{
x = find(x), y = find(y);
if (x == y)
return;
//小的併入大的
if (size[x] < size[y])
{
p[x] = y;
size[y] += size[x];
}
else
{
p[y] = x;
size[x] += size[y];
}
}
inline bool are_friends(int x, int y)
{
return find(x) == find(y);
}
inline bool are_enemies(int x, int y)
{
return find(get_ene(x)) == find(y) || find(get_ene(y)) == find(x);
}
inline bool set_friends(int x, int y)
{
int ex = find(get_ene(x)), ey = find(get_ene(y));
x = find(x), y = find(y);
if (ex == y || ey == x) //they are enemies
return false;
do_union(x, y);
do_union(ex, ey); //雙方的敵人互為朋友
return true;
}
inline bool set_enemies(int x, int y)
{
int ex = find(get_ene(x)), ey = find(get_ene(y));
x = find(x), y = find(y);
if (x == y) //they are friends
return false;
//敵人的敵人就是朋友
do_union(ex, y);
do_union(ey, x);
return true;
}
int main()
{
scanf("%d", &n);
init();
int c, x, y;
while (scanf("%d%d%d", &c, &x, &y) && c)
{
if (c == 1)
{
if (!set_friends(x, y))
puts("-1");
}
else if (c == 2)
{
if (!set_enemies(x, y))
puts("-1");
}
else if (c == 3)
puts(are_friends(x, y) ? "1" : "0");
else if (c == 4)
puts(are_enemies(x, y) ? "1" : "0");
}
return 0;
}
(2)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
//disjoint set
int p[N]; //the leader of each unit([x]: x 的代表)
int size[N]; //number of each group([x]: x 的成員有幾人)
int enemy[N]; //[x]: x's enemy
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
{
size[i] = 1;
p[i] = i;
enemy[i] = 0; //empty set
}
}
inline int find(int x)
{
return (x == p[x]) ? x : (p[x] = find(p[x]));
}
inline void do_union(int x, int y)
{
x = find(x), y = find(y);
if (x == y || !x || !y)
return;
//小的併入大的
if (size[x] < size[y])
{
p[x] = y;
size[y] += size[x];
//size[x] = 0;
}
else
{
p[y] = x;
size[x] += size[y];
//size[y] = 0;
}
}
inline bool are_friends(int x, int y)
{
x = find(x), y = find(y);
return x == y;
}
inline bool are_enemies(int x, int y)
{
x = find(x), y = find(y);
return find(enemy[x]) == y || find(enemy[y]) == x;
}
inline bool set_friends(int x, int y)
{
x = find(x), y = find(y);
int ex = find(enemy[x]), ey = find(enemy[y]);
if (ex == y || ey == x) //they are enemies
return false;
do_union(x, y);
//兩方的敵人會成為朋友，並更新紀錄敵人的陣列
do_union(ex, ey);
ex = find(ex), ey = find(ey);
enemy[find(x)] = ex ? ex : ey;
return true;
}
inline bool set_enemies(int x, int y)
{
x = find(x), y = find(y);
if (x == y) //they are friends
return false;
do_union(enemy[x], y);
do_union(enemy[y], x);
x = find(x), y = find(y);
enemy[x] = y;
enemy[y] = x;
return true;
}
int main()
{
int n;
scanf("%d", &n);
init(n);
int c, x, y;
while (scanf("%d%d%d", &c, &x, &y) && c)
{
++x, ++y; //編號從 1 開始
if (c == 1)
{
if (!set_friends(x, y))
puts("-1");
}
else if (c == 2)
{
if (!set_enemies(x, y))
puts("-1");
}
else if (c == 3)
puts(are_friends(x, y) ? "1" : "0");
else if (c == 4)
puts(are_enemies(x, y) ? "1" : "0");
}
return 0;
}