# acwing 239. 奇偶游戏 并查集

#### 输出格式

数据范围
N≤10^9,M≤10000

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

3


1 数据范围过大  有 10^9
2 询问的内容如何转化到并查集


1 #include
2 #include
3 #include
4
5 using namespace std;
6
7 const int MAX_M = 20010;
8
9 int N, M;
10 int n, m;
11
12 int fa[MAX_M];
13 int d[MAX_M];
14
15 int idx = 0;
16
17 unordered_map S;
18
19
20 //离散化
21 int get(int x) {
22     if (S.count(x) == 0) S[x] = ++idx;
23     return S[x];
24 }
25
26 void init()
27 {
28     for (int i = 0; i > n >> m;
48     int res = m;
49     init();
50     for (int i = 1; i > a >> b >> s;
53         a = get(a - 1); b = get(b);
54         int pa = find(a), pb = find(b);
55
56         if (pa == pb) {
57             //查看两者是否符合之前的信息
58             if (s == "even")
59             {
60                 //两者奇偶性相同
61                 if( (d[a] + d[b]) % 2 != 0){
62                     //有矛盾
63                     res = i - 1;
64                     break;
65                 }
66             }
67             else if (s == "odd") {
68                 //两者奇偶性不同
69                 if ((d[a] + d[b]) % 2 != 1) {
70                     //有矛盾
71                     res = i - 1;
72                     break;
73                 }
74             }
75             else {
76                 cout << s << endl;
77                 cout << "error" << endl;
78                 break;
79             }
80         }
81         else {
82             //pa != pb
83             //合并
84             fa[pa] = pb;
85             int add = 0;
86             if (s == "odd") add = 1;
87             d[pa] = (d[a] + d[b] + add)%2;
88         }
89
90
91     }
92     cout << res << endl;
93
94
95
96     return 0;
97 }