Parity game POJ - 1733

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 #define ll long long
11 #define pb push_back
12 #define fi first
13 #define se second
14 
15 
16 const int N = 5010 << 1;
17 struct node
18 {
19     int rt, v;
20 }fa[N];
21 struct info
22 {
23     int x, y, d;
24 };
25 vector<info > a;
26 vector<int > id;
27 int n, m;
28 
29 int Find(int x)
30 {
31     if(fa[x].rt == x) return x;
32     else{
33         int tmp = fa[x].rt;
34         fa[x].rt = Find(tmp);
35         fa[x].v = (fa[x].v + fa[tmp].v) % 2;
36         return fa[x].rt;
37     }
38 }
39 
40 bool Union(int x, int y, int d)
41 {
42     int fax = Find(x);
43     int fay = Find(y);
44     if(fax != fay){
45         fa[fay].rt = fax;
46         fa[fay].v = (fa[x].v + d - fa[y].v + 2) % 2;
47         return true;
48     }else{
49         if(0 == (fa[x].v + d - fa[y].v + 2) % 2) return true;
50         else return false;
51     }
52 }
53 
54 void solve()
55 {   
56     scanf("%d%d", &n, &m);
57     int x, y;
58     char op[10];
59     for(int i = 1; i <= m; ++i){
60         scanf("%d%d%s", &x, &y, op);
61         id.pb(x);
62         id.pb(y);
63         a.pb({x, y, op[0] == ‘e‘ ? 0 : 1});
64     }
65     sort(id.begin(), id.end());
66     id.erase(unique(id.begin(), id.end()), id.end());
67     int n = id.size();
68 
69     for(int i = 0; i <= n; ++i){
70         fa[i].rt = i;
71         fa[i].v = 0;
72     }
73 
74     int inx = -1;
75     for(int i = 0; i < m; ++i){
76         int x = lower_bound(id.begin(), id.end(), a[i].x) - id.begin() + 1;
77         int y = lower_bound(id.begin(), id.end(), a[i].y) - id.begin() + 1;
78         if(!Union(x - 1, y, a[i].d)){
79             inx = i;
80             break;
81         } 
82     }
83     
84     //printf("ans = %d\n", inx == -1 ? m : inx);
85     printf("%d\n", inx == -1 ? m : inx);
86 }
87 
88 int main()
89 {
90 
91     solve();
92 
93     return 0;
94 }