分析：经典并查集
|
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 |
#include <stdio.h>#include<iostream>using
namespace std;const
int MAX_N = 50010;int set[MAX_N];int r[MAX_N];void
init(int
n){ for
(int i = 0; i <= n; i++) { set[i] = i; r[i] = 0; }}int
cha(int
x){ if
(x == set[x]) return
x; int
tx = cha(set[x]); r[x] = (r[x] + r[set[x]]) % 3; return
set[x] = tx;}void
unite(int
x, int
y, int
type){ int
tx = cha(x); int
ty = cha(y); set[ty] = tx; r[ty] = (r[x] + type - 1 - r[y] + 3) % 3; return;}int
main(){ int
n(0), m(0); int
xx; scanf("%d",&xx); while(xx--) { scanf("%d%d", &n, &m); init(n); int
type(0), x(0), y(0); int
ans(0); for
(int i = 1; i <= m; i++) { scanf("%d%d%d", &type, &x, &y); if
(x > n || y > n || (type == 2 && x == y)) { ans++; continue; } if
(cha(x) == cha(y)) { if
((r[y] - r[x] + 3) % 3 != (type - 1)) { ans++; } } else { (unite(x, y, type)); } } printf("%d\n", ans); }} |
携程编程大赛 （预赛第二场）第一题【剪刀石头布】,布布扣,bubuko.com
原文：http://www.cnblogs.com/castledrv/p/3664011.html