POJ 1182

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int MAX_N = 50005;
 9 int N,K,ch,a,b,ans = 0;
10 int f[MAX_N * 3];
11 
12 int _find(int x) {
13         return x == f[x] ? x : f[x] = _find(f[x]);
14 }
15 
16 void _union(int x,int y) {
17         int u = _find(x),v = _find(y);
18         f[u] = v;
19 }
20 
21 bool same(int x,int y) {
22         int u = _find(x),v = _find(y);
23         return u == v;
24 }
25 
26 void solve() {
27         if (a < 0 || a >= N || b < 0 || b >= N) {
28                 ++ans;
29                 return;
30         }
31 
32         if (ch == 1) {
33                 if(same(a,b + N) || same(a,b + 2 * N)) {
34                         ++ans;
35                 } else {
36                         _union(a,b);
37                         _union(a + N,b + N);
38                         _union(a + 2 * N,b + 2 * N);
39                 }
40         }
41         if (ch == 2) {
42                 if(same(a,b) || same(a,b + 2 * N)) {
43                         ++ans;
44                 } else {
45                         _union(a,b + N);
46                         _union(a + N,b + 2 * N);
47                         _union(a + 2 * N,b);
48                 }
49         }
50 
51 }
52 
53 
54 int main()
55 {
56     //freopen("sw.in","r",stdin);
57     scanf("%d%d",&N,&K);
58 
59     for (int i = 1; i <= 3 * N; ++i) f[i] = i;
60     for (int i = 1; i <= K; ++i) {
61             scanf("%d%d%d",&ch,&a,&b);
62             //printf("%d %d %d\n",ch,a,b);
63             --a;--b;
64             solve();
65 
66     }
67 
68     printf("%d\n",ans);
69     return 0;
70 }