poj 1182食物連鎖(および調査集)

タイトル接続:
　　 http://poj.org/problem?id=1182
テーマ:
中国語のテーマ、テーマの意味は私はくだらないことを言わない.
問題解決の考え方:
この問題に出会ったのは先月下旬だったようで、その時見たらまた休みに間に合うのではなく、ずっと置いていたので、今になっています.
集合の性質から,1つの集合の中の任意の2つの要素には必ず対応関係があり,関係がなければ1つの集合に統合されないことが分かる.
xをfatherで表し、yが1つの集合の中にあるかどうか、nexuでx,yの関係を表し、nexu[x]はxとxの親ノードの関係を表し、(xがその親ノードと同級であればnexu[x]=0;xが
その親ノードは食べて、nexu[x]=1;どうせxはその親ノードを食べることができて、nexu[x]=2;)この問題は主に経路圧縮の時の親ノードの変化、引き起こすnexuノードの変化を解決します.
http://blog.sina.com.cn/s/blog_807ca3aa0100tumm.html、神牛微博里が詳しく話しています.ps:以前は単一のインスタンスをマルチインスタンスとして書くとwaができませんでしたが、このテーマはできます.

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 50005;
 8 int father[maxn], nexu[maxn], n;
 9 void init ();
10 int find (int x);
11 bool judge (int d, int x, int y);
12 int main ()
13 {
14     int k, s, x, y;
15     scanf ("%d %d", &n, &k);
16     init ();
17     int sum = 0;
18     while (k --)
19     {
20         scanf ("%d %d %d", &s, &x, &y);
21         if (judge (s-1, x, y))
22             sum ++;
23     }
24     printf ("%d
", sum);
25     return 0;
26 }
27 
28 void init ()
29 {
30     memset (nexu, 0, sizeof(nexu));//    0，          
31     for (int i=0; i<maxn; i++)
32         father[i] = i;
33 }
34 
35 int find (int x)
36 {
37     if (x != father[x])
38     {
39         int tx = find (father[x]);//       ，nexu[x]       
40         nexu[x] = (nexu[x] + nexu[father[x]])%3;
41         father[x] = tx;
42 
43     }
44     return father[x];
45 }
46 
47 bool judge (int d, int x, int y)
48 {
49     if (x>n || y>n)
50         return true;
51     if (d && x == y)
52         return true;
53     int px = find (x);
54     int py = find (y);
55     int num = (nexu[y] - nexu[x] + 3) % 3;
56     if (px == py )
57         if (num != d)
58             return true;
59         else
60             return false;
61     father[py] = px;//          
62     nexu[py] = (nexu[x] + d - nexu[y] + 3) % 3;
63     return false;
64 }