1、poj 2236 Wireless Network

　　题意：一张图上分布着n台坏了的电脑，并知道它们的坐标。两台修好的电脑如果距离<=d就可以联网，也可以通过其他修好的电脑间接相连。给出操作“O x”表示修好x，给出操作“S x y”，请你判断x和y在此时有没有连接上。

　　思路：简单并查集。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int n, d; 7 const int maxn = 1200; 8 int pre[maxn]; 9 struct node10 {11     int x;12     int y;13 }cpt[maxn];14 int Find(int x)15 {16     int r = x;17     while (r != pre[r])18     {19         r = pre[r];20     }21     int i = x, j;22     while (pre[i] != r)23     {24         j = pre[i];25         pre[i] = r;26         i = j;27     }28     return r;29 }30 void Join(int x, int y)31 {32     int px = Find(x), py = Find(y);33     if (px != py) pre[px] = py;34 }35 int main()36 {37     while (~scanf("%d%d", &n, &d))38     {39         for (int i = 1; i <= n; i++) scanf("%d%d", &cpt[i].x, &cpt[i].y);40         memset(pre, 0, sizeof(pre));41         char op[3];42         while (~scanf("%s", op))43         {44             if (op[0] == 'O')45             {46                 int p;47                 scanf("%d", &p);48                 pre[p] = p;49                 for (int i = 1; i <= n; i++)50                 {51                     if (i == p)continue;52                     double dis = sqrt(1.0*(cpt[i].x - cpt[p].x)*(cpt[i].x - cpt[p].x) + (cpt[i].y - cpt[p].y)*(cpt[i].y - cpt[p].y));53                     if (dis <= d&&pre[i]!=0)54                     {55                         Join(i, p);56                     }57                 }58             }59             else60             {61                 int p, q;62                 scanf("%d%d", &p, &q);63                 if (Find(p) != Find(q))printf("FAIL\n");64                 else printf("SUCCESS\n");65             }66         }67     }68     return 0;69 }
         
        
       
      

2、poj 1611 The Suspects

　　题意：有一个学校，有N个学生，编号为0-N-1，现在0号学生感染了非典，凡是和0在一个社团的人就会感染，并且这些人如果还参加了别的社团，他所在的社团照样全部感染，求感染的人数。

　　思路：并查集，合并的时候顺便统计人数。

1 #include
      
        2 using namespace std; 3 const int maxn = 30010; 4 int pre[maxn]; 5 int Cnt[maxn]; 6 int Find(int x) 7 { 8     int r = x; 9     while (r != pre[r])10     {11         r = pre[r];12     }13     int i = x, j;14     while (pre[i] != r)15     {16         j = pre[i];17         pre[i] = r;18         i = j;19     }20     return r;21 }22 void Join(int x, int y)23 {24     int fx = Find(x), fy = Find(y);25     if (fx != fy) pre[fx] = fy,Cnt[fy]+=Cnt[fx];26 }27 int main()28 {29     int n, m;30     while (~scanf("%d%d", &n, &m))31     {32         for (int i = 0; i <= n; i++) pre[i] = i,Cnt[i]=1;33         if (n == 0 && m == 0)break;34         for (int i = 0; i < m; i++)35         {36             int k;37             scanf("%d", &k);38             int pre, now;39             for (int i = 0; i < k; i++)40             {41                 int x;42                 scanf("%d", &x);43                 if (i == 0) pre = now = x;44                 else45                 {46                     now = x;47                     Join(now, pre);48                     pre = now;49                 }50             }51         }52         //int cnt = 0;53         //for (int i = 0; i < n; i++)54         //{55         //    if (Find(i) == Find(0)) cnt++;56         //}57         printf("%d\n", Cnt[Find(0)]);58     }59     return 0;60 }
      

3、hdu 1213 How Many Tables

　　题意：两个人若互相认识，则坐在同一张桌子上。问需要多少张桌子。

　　思路：并查集，合并的时候更新剩余连通块。

1 #include
      
        2 using namespace std; 3 const int maxn = 1010; 4 int pre[maxn]; 5 int cnt; 6 int Find(int x) 7 { 8     int r = x; 9     while (r != pre[r])10     {11         r = pre[r];12     }13     int i = x, j;14     while (pre[i] != r)15     {16         j = pre[i];17         pre[i] = r;18         i = j;19     }20     return r;21 }22 void Join(int x, int y)23 {24     int fx = Find(x), fy = Find(y);25     if (fx != fy) pre[fx] = fy, cnt--;26 }27 int main()28 {29     int t;30     scanf("%d", &t);31     while (t--)32     {33         int n, m;34         scanf("%d%d", &n, &m);35         cnt = n;36         for (int i = 1; i <= n; i++) pre[i] = i;37         for (int i = 0; i < m; i++)38         {39             int x, y;40             scanf("%d%d", &x, &y);41             Join(x, y);42         }43         printf("%d\n", cnt);44     }45     return 0;46 }
      

4、hdu 3038 How Many Answers Are Wrong

　　题意：给你M个区间和，问你有几个是与前面矛盾的。

　　思路：带权并查集，利用并查集形成集合树,利用sum数组记录集合树中当前节点i到根之间的边的权值和,如果当前两个节点不在同一棵集合树中,那么通过两个集合树合并,调整权值,使能够保证合法的,所以只需要合并,将一棵树的根变为另一棵树的根的子节点,然后建边,因为f[i]<i,i<j,f[j]<j,所以s=sum[j]+sum[f[j]]-sum[i]因为当前j的根是f[j],所以要加上新加的边权,那么新的边权既可以通过这个方程求取即可。

1 //利用并查集形成集合树,利用sum数组记录集合树中当前节点i到根之间的边的权值和,如果当前两个节点不在同一棵集合树中,那么通过两个集合树合并,调整权值,使能够保证合法的,所以只需要合并,将一棵树的根变为另一棵树的根的子节点,然后建边,因为f[i]
      
       
        
          3 #define MAXN 200010 4 int f[MAXN], r[MAXN]; 5 int find(int x) 6 { 7     if (x == f[x]) 8         return f[x]; 9     int t = find(f[x]);10     r[x] = r[x] + r[f[x]];//这里首先要对这个递归的过程很了解，当递归到某一层时，x还未接到根节点上，所以r[x]表示的是x到f[x]的距离，经上一步操作，f[x]已经接到根节点上了，所以r[f[x]]表示的是父节点到根节点的距离所以x到根节点的距离就直接等于r[x]+r[f[x]]11     f[x] = t;12     return f[x];13 }14 int fun(int x, int y)15 {16     if (x>y)17         return x - y;18     else y - x;19 }20 int Union(int x, int y, int sum)21 {
    //传进来时x
        
       
      

5、poj 1182 食物链

　　题意：有  3  种动物，互相吃与被吃，现在告诉你  m  句话，其中有真有假，叫你判断假的个数  (  如果前面没有与当前话冲突的，即认为其为真话  )。每句话开始都有三个数 D A B，当D = 1时，表示A 和B是同类，当D = 2时表示A 吃 B。

　　思路：带权并查集。

1 #include
      
        2 using namespace std; 3 const int maxn = 50010; 4 int n,k; 5 int pre[maxn], r[maxn]; 6 //根据“x与p[x]能否确定两者之间的关系”来划分，若能确定x与p[x]的关系，则它们同属一个集合。 7 //p[x]表示x的根结点。r[x]表示p[x]与x的关系。r[x] == 0 表示p[x]与x同类；1表示p[x]吃x；2表示x吃p[x]。 8 void Init() 9 {10     for (int i = 0; i <= n; i++)11     {12         pre[i] = i;13         r[i] = 0;14     }15 }16 17 //每次通过儿子对父亲的关系，父亲对爷爷的关系，得到儿子对爷爷的关系18 int Find(int x)19 {20     if (pre[x] == x) return x;21     else22     {23         int fa = pre[x];24         pre[x] = Find(fa);25         r[x] = (r[x] + r[fa]) % 3;26         return pre[x];27     }28 }29 30 bool Union(int x, int y, int d)31 {
    //d=1：x和y是同类；d=2,x吃y32     int rx = Find(x), ry = Find(y);33     if (rx == ry)return true;34     else35     {36         pre[ry] = rx;37         r[ry] = (r[x] - r[y] + 2 + d) % 3;38         //r[ry]=(3-r[y]+(d-1)+r[x])%3(可推)39         return false;40     }41 }42 43 int main()44 {45     scanf("%d%d", &n, &k);46     Init();47     int cnt = 0;48     while (k--)49     {50         int d, x, y;51         scanf("%d%d%d", &d, &x, &y);52         if (x > n || y > n) cnt++;53         else54         {55             bool same = Union(x, y, d);56             if (same)57             {58                 if (d == 1)59                 {60                     //D == 1 表示X与Y为同类，而从r[X] != r[Y]可以推出 X 与 Y 不同类。矛盾。61                     if (r[x] != r[y])62                     {63                         cnt++;64                     }65                 }66                 else67                 {68                     if ((r[y] + 3 - r[x]) % 3 != 1)69                     {
    //（X 与Y为同类）或者　r[X] == ( r[Y] + 1 ) % 3 （Y吃X ）则此话为假。70                         cnt++;71                     }72                 }73             }74         }75     }76     printf("%d\n", cnt);77     return 0;78 }
      

6、poj 1417 True Liars(并查集+DP)

　　题意：给出p1+p2个人，其中p1个是好人，p2个是坏人。然后有一些关系 ，a说b是好人(坏人).其中没有矛盾的，判断是否有唯一解判断哪些人是好人，哪些人是坏人。其中比较重要的是，好人总说真话，坏人总说假话。

　　思路：

　　①一个人说另一个人是好人，那么如果这个人是好人，说明 对方确实是好人，如果这个是坏人，说明这句话是假的，对方也是坏人。

　　②如果一个人说另一个人是坏人，那么如果这个人是好人，说明对方是坏人，如果这个是坏人，说明 对方是好人。

也就是如果条件是yes说明这两个是相同集合的，否则是两个不同的集合。用r[i]表示i结点与根结点的关系，0为相同集合，1为不同集合。

通过并查集，可以将所有人分为若干个集合，其中对于每一个集合，又分为两个集合（好人和坏人，但是不知道哪些是好人，哪些是坏人，我们只有相对关系）

用dp[i][j]表示前i个集合中好人为j的种数，如果dp[cnt][p1]！=1说明方案不唯一，或者无解。belong[i][0]表示i属于哪个大类，belong[i][1]表示i属于该大类的哪一个小类，choose[i]倒推找出选择的大集合i的两类中是哪一类,然后升序输出好人的编号。

1 #include
      
         2 using namespace std;  3 int n, p1, p2;  4 const int maxn = 1100;  5 int pre[maxn];//i的父亲  6 int r[maxn];//i和pre[i]的关系  7 //0:同类；1:不同类  8   9 bool vis[maxn]; 10  11 int cntnum[maxn][2];//cntnum[i][j]表示把第i个集合分成两个部分的人数 12  13 int dp[maxn][310];//dp[i][j]表示前i个集合中好人为j的种数 14  15 int belong[maxn][2];//belong[i][0]表示i属于哪个大类，belong[i][1]表示i属于该大类的哪一个小类（对应cntnum） 16 int id[maxn]; 17 //根据孩子与父亲，父亲与祖父之间的关系可以推出孩子与祖父的关系 18 int Find(int x) 19 { 20     if (pre[x] == x) return x; 21     else 22     { 23         int fa = pre[x]; 24         pre[x] = Find(fa); 25         r[x] = r[x] ^ r[fa]; 26         return pre[x]; 27     } 28 } 29  30 void Union(int x, int y, int k) 31 { 32     int rx = Find(x), ry = Find(y); 33     if (rx != ry) 34     { 35         pre[rx] = ry; 36         r[rx] = (r[x] - r[y] + 2 + k) % 2; 37     } 38 } 39  40 void Init() 41 { 42     for (int i = 0; i <= p1 + p2; i++) 43     { 44         pre[i] = i; 45         r[i] = 0; 46     } 47 } 48 int main() 49 { 50     while (~scanf("%d%d%d", &n, &p1, &p2)) 51     { 52         if (n == 0 && p1 == 0 && p2 == 0) break; 53         Init(); 54         char s[5]; 55         int a, b, k; 56         for (int i = 0; i < n; i++) 57         { 58             scanf("%d%d%s", &a, &b, s); 59             if (s[0] == 'y') k = 0; 60             else k = 1; 61             Union(a, b, k); 62         } 63         //处理完后，得到若干个集合，每个集合中两两同类或不同类 64         //2：找到有多少个大集合，每个大集合中同类及不同类的个数 65         memset(vis, 0, sizeof(vis)); 66         memset(cntnum, 0, sizeof(cntnum)); 67         memset(belong, 0, sizeof(belong)); 68  69         int cnt = 0; 70         for (int i = 1; i <= p1 + p2; i++) 71         { 72             if (!vis[i]) 73             { 74                 cnt++; 75                 int f = Find(i); 76                 id[f] = cnt;//对每个大集合的根进行分类 77                 for (int j = i; j <= p1 + p2; j++) 78                 { 79                     if (Find(j) == f) 80                     { 81                         vis[j] = true; 82                         cntnum[cnt][r[j]]++; 83                         belong[j][0] = cnt; 84                         belong[j][1] = r[j]; 85                     } 86                 } 87             } 88         } 89         //DP 90         memset(dp, 0, sizeof(dp)); 91         dp[0][0] = 1; 92         for (int i = 1; i <= cnt; i++) 93         { 94             for (int j = p1; j >= 0; j--) 95             { 96                 if (j - cntnum[i][0] >= 0 && dp[i - 1][j - cntnum[i][0]] > 0) 97                 { 98                     dp[i][j] += dp[i - 1][j - cntnum[i][0]]; 99                 }100                 if (j - cntnum[i][1] >= 0 && dp[i - 1][j - cntnum[i][1]] > 0)101                 {102                     dp[i][j] += dp[i - 1][j - cntnum[i][1]];103                 }104             }105         }106 107         //输出108         if (dp[cnt][p1] != 1) printf("no\n");109         else110         {111             int choose[maxn];//倒推找出选择的大集合的两类中是哪一类112             int totalpeople = p1;113             for (int i = cnt; i >= 1; --i)114             {115                 if (dp[i][totalpeople] == dp[i - 1][totalpeople - cntnum[i][0]])116                 {117                     choose[i] = 0;118                     totalpeople -= cntnum[i][0];119                 }120                 else if (dp[i][totalpeople] == dp[i - 1][totalpeople - cntnum[i][1]])121                 {122                     choose[i] = 1;123                     totalpeople -= cntnum[i][1];124                 }125             }126 127             for (int i = 1; i <= p1 + p2; i++)128             {129                 int fa = Find(i);130                 int set_id = id[fa];131                 if (belong[i][0] == set_id&&belong[i][1] == choose[set_id])132                 {133                     printf("%d\n", i);134                 }135             }136             printf("end\n");137         }138     }139     return 0;140 }
      

7、poj 1456 Supermarket

　　题意：有N件商品，分别给出商品的价值和销售的最后期限，只要在最后日期之前销售处，就能得到相应的利润，并且销售该商品需要1天时间。问销售的最大利润。

　　思路：先把所有产品按照利润从大到小排序，假设一个产品a占用了一个日期后，那么如果下次又有一个产品b和产品a的截止日期是相同的，但是那个日期以被占用了，所以就要往前移动1天，那么就可以用并查集进行标记，在a占用了那个日期后，把a的截止日期指向前一个日期，这样的话，可以直接查找到他要占用到哪一个时间。

1 #include
      
        2 #include
       
         3 using namespace std; 4 int n; 5 const int maxn = 10010; 6 const int maxt = 10010; 7 struct node 8 { 9     int pi;10     int di;11 }goods[maxn];12 13 int pre[maxt];14 int Find(int x)15 {16     int r = x;17     while (r != pre[r])18     {19         r = pre[r];20     }21     int i = x, j;22     while (pre[i] != r)23     {24         j = pre[i];25         pre[i] = r;26         i = j;27     }28     return r;29 }30 31 void Union(int x, int y)32 {33     int fx = Find(x), fy = Find(y);34     if (fx != fy)35     {36         if (fx < fy) pre[fy] = fx;37         else pre[fx] = fy;38     }39 }40 41 42 void Init()43 {44     for (int i = 0; i 
        
          b.di;52     else return a.pi > b.pi;53 }54 int main()55 {56     while (~scanf("%d", &n))57     {58         Init();59         for (int i = 0; i < n; i++)60         {61             scanf("%d%d", &goods[i].pi, &goods[i].di);62         }63         sort(goods, goods + n, Cmp);64 65         int sum = 0;66         67         for (int i = 0; i < n; i++)68         {69             int tt = goods[i].di;70             int ff = Find(tt);71             if (ff > 0)72             {73                 Union(ff, ff - 1);74                 sum += goods[i].pi;75             }76         }77         printf("%d\n", sum);78     }79     return 0;80 }
        
       
      

8、poj 1703 Parity game

　　题意：有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的。

　　思路：将[l,r]这个区间化为(l-1,r]，那么1的个数就可以表示为sum[r]-sum[l-1]，也就确定了奇偶性，我们可以用r[]数组表示这个端点到它的根节点的1的奇偶（这个区间就是(i,root(i)]（0代表偶，1代表奇）  对于每个输入的区间，我们查找它们的根节点是否相同。

          ①如果相同，证明这个区间的奇偶性在之前已经得知，那么直接判断即可

          ②如果不同，那么就是u-1与v此时不在同一个集合中，则合并时更新r[].

1 #include
      
        2 #include
       
         3 using namespace std; 4 int n, m; 5 const int maxn = 5050; 6 int pre[maxn]; 7 int val[maxn]; 8 struct node 9 {10     int ll;11     int rr;12     int d;13 }qry[maxn];14 int Map[maxn * 2];15 int Find(int x)16 {17     if (x == pre[x]) return x;18     else19     {20         int fa = pre[x];21         pre[x] = Find(fa);22         val[x] = (val[x] + val[fa]) % 2;23         return pre[x];24     }25 }26 bool Union(int x, int y, int v)27 {
    //x
       
      

9、poj 1984 Navigation Nightmare

　　题意：图上有一些村庄，村庄之间用只能指向东南西北的方向的道路连接，村庄只能位于道路的两端。询问截止到第I个已知条件时某两个村庄之间的曼哈顿距离。

　　思路：先根据道路设出每个点的坐标，然后如果某个已知条件已知，则合并。询问时判断两个村庄是否在同一个连通块即可。

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 int n, m,k;  6 const int maxn = 40050;  7 const int maxm = 40050;  8 const int maxk = 10050;  9 struct qry 10 { 11     int t; 12     int f1; 13     int f2; 14     int id; 15 }qrys[maxk]; 16 int ans[maxk]; 17  18 struct stp 19 { 20     int f1; 21     int f2; 22     stp(int ff1 = 0, int ff2 = 0) :f1(ff1), f2(ff2) 23     { 24     } 25 }; 26 vector
         
          stps; 27 struct pt 28 { 29     int x; 30     int y; 31 }points[maxn]; 32 bool Cmp1(const qry&a, const qry&b) 33 { 34     return a.t < b.t; 35 } 36  37 int pre[maxn]; 38 int Find(int x) 39 { 40     if (pre[x] == x) return x; 41     else 42     { 43         int fa = pre[x]; 44         pre[x] = Find(fa); 45         return pre[x]; 46     } 47 } 48 bool Union(int x, int y) 49 { 50     int fx = Find(x), fy = Find(y); 51     if (fx == fy) return true; 52     else 53     { 54         pre[fx] = fy; 55         return false; 56     } 57 } 58 struct node 59 { 60     int to; 61     char dir; 62     int len; 63     node(int tt=0,char c=0,int ll=0):to(tt),dir(c),len(ll){ } 64 }; 65 vector
          
           mp[maxn]; 66 bool vis[maxn]; 67 void DFS(int r) 68 { 69  70     int sz = mp[r].size(); 71     for (int i = 0; i < sz; i++) 72     { 73         int tx = points[r].x, ty = points[r].y; 74         int v = mp[r][i].to, length = mp[r][i].len; 75         if (vis[v])continue; 76         switch (mp[r][i].dir) 77         { 78         case 'N':tx -= length; 79             break; 80         case 'E': ty += length; 81             break; 82         case 'S':tx += length; 83             break; 84         case 'W':ty -= length; 85             break; 86         } 87         points[v].x = tx, points[v].y = ty; 88         vis[v] = true; 89         DFS(v); 90     } 91 } 92  93 int main() 94 { 95     while (~scanf("%d%d", &n, &m)) 96     { 97         for (int i = 0; i <= n; i++) mp[i].clear(); 98         stps.clear(); 99         for (int i = 1; i <= m; i++)100         {101             int u, v, l;102             char op[10];103             scanf("%d%d%d%s", &u, &v, &l,op);104             mp[u].push_back(node(v, op[0], l));105             char nc;106             switch (op[0])107             {108             case 'N':109                 nc = 'S';110                 break;111             case 'S':112                 nc = 'N';113                 break;114             case 'E':115                 nc = 'W';116                 break;117             case 'W':118                 nc = 'E';119                 break;120             }121             mp[v].push_back(node(u, nc, l));122             stps.push_back(stp(u, v));123         }124         memset(vis, 0, sizeof(vis));125         for (int i = 0; i <= n; i++)126         {127             if (mp[i].size())128             {129                 points[i].x = 0, points[i].y = 0;130                 vis[i] = true;131                 DFS(i);132                 break;133             }134         }135         scanf("%d", &k);136         for (int i = 0; i < k; i++)137         {138             scanf("%d%d%d",&qrys[i].f1, &qrys[i].f2, &qrys[i].t);139             qrys[i].id = i + 1;140         }141         sort(qrys, qrys + k, Cmp1);142 143         for (int i = 0; i <= n; i++) pre[i] = i;144         int nowstep = 0;145         for (int i = 0; i < k; i++)146         {147             int t = qrys[i].t;148             for (; nowstep < t; nowstep++)149             {150                 int f1 = stps[nowstep].f1;151                 int f2 = stps[nowstep].f2;152                 Union(f1, f2);153             }154             int x = qrys[i].f1, y = qrys[i].f2;155             int fx = Find(x), fy = Find(y);156             if (fx != fy)157             {158                 ans[qrys[i].id] = -1;159             }160             else ans[qrys[i].id] = abs(points[x].x - points[y].x) + abs(points[x].y - points[y].y);161         }162         for (int i = 1; i <= k; i++)163         {164             printf("%d\n", ans[i]);165         }166     }167     return 0;168 }
          
         
        
       
      

10、hdu 1829 A Bug's Life

　　题意：给定一系列数对，例如a和b，表示a和b不是同一种性别，然后不断的给出这样的数对，问有没有矛盾的情况。

　　思路：带权并查集。

1 #include
      
        2 using namespace std; 3 const int maxn = 2100; 4 int pre[maxn]; 5 int r[maxn]; 6 int n, m; 7 void Init() 8 { 9     for (int i = 0; i <= n; i++)10     {11         pre[i] = i;12         r[i] = 0;13     }14 }15 int Find(int x)16 {17     if (pre[x] == x)return x;18     else19     {20         int fa = pre[x];21         pre[x] = Find(fa);22         r[x] = r[x] ^ r[fa];23         return pre[x];24     }25 }26 27 bool Join(int x, int y)28 {29     int fx = Find(x), fy = Find(y);30     if (fx == fy)return true;31     else32     {33         pre[fx] = fy;34         r[fx] = r[x] ^ r[y] ^ 1;35         return false;36     }37 }38 int main()39 {40     int t;41     int Case = 1;42     scanf("%d", &t);43     while (t--)44     {45         scanf("%d%d", &n, &m);46         Init();47         bool flag = true;48         while (m--)49         {50             int u, v;51             scanf("%d%d", &u, &v);52             if (!flag)continue;53             if (Join(u, v))54             {55                 if (r[u] ^ r[v] != 1)56                 {57                     flag = false;58                 }59             }60         }61         if (flag) printf("Scenario #%d:\nNo suspicious bugs found!\n\n", Case++);62         else printf("Scenario #%d:\nSuspicious bugs found!\n\n", Case++);63     }64     return 0;65 }
      

11、poj 2912 Rochambeau

　　题意：有N个人玩剪刀石头布，其中有个人是裁判，其他人分为3组。 这3组中每个组分别出剪刀，石头和布。 裁判可以任意出3个中的一个。 现在有M个回合，每个回合从N个人中任意选出两个人来玩，并给出结果。 要求输出最早找出裁判的回合数，以及裁判的编号。还有可能无法确定。

　　思路：利用并查集建立起相对关系，枚举裁判是哪一个，对有他参与的回合不予处理，如果在他不参与的回合中出现了矛盾，那么这个人一定就不是裁判。

1 #include
      
        2 using namespace std; 3 const int maxn = 510; 4 const int maxm = 2010; 5 int n, m; 6 int pre[maxn]; 7 int r[maxn];//0：平局；1：pre[x]赢了x;2:x赢了pre[x] 8 void Init() 9 {10     for (int i = 0; i <= n; i++)11     {12         pre[i] = i;13         r[i] = 0;14     }15 }16 struct stp17 {18     int u;19     int v;20     int d;21 }stps[maxm];22 23 int ok[maxn];24 25 int Find(int x)26 {27     if (pre[x] == x)return x;28     else29     {30         int fa = pre[x];31         pre[x] = Find(fa);32         r[x] = (r[x] + r[fa]) % 3;33         return pre[x];34     }35 }36 bool Union(int x, int y,int d)37 {38     int fx = Find(x), fy = Find(y);39     if (fx == fy)return true;40     else41     {42         pre[fx] = fy;43         r[fx] = (3 - r[x] + d + r[y]) % 3;44         return false;45     }46 }47 int main()48 {49     while (~scanf("%d%d", &n, &m))50     {51         for (int i = 0; i < m; i++)52         {53             int u, v,d;54             char c;55             scanf("%d%c%d", &u, &c, &v);56             if (c == '=')d = 0;57             else if (c == '<') d = 1;58             else d = 2;59             stps[i].u = u, stps[i].v=v, stps[i].d=d;60         }61         memset(ok, 0, sizeof(ok));62         for (int i = 0; i < n; i++)63         {64             Init();65             for (int j = 0; j < m; j++)66             {67                 if (stps[j].u == i || stps[j].v == i)continue;68                 if (Union(stps[j].u, stps[j].v, stps[j].d))69                 {70                     if ((r[stps[j].u]+3-r[stps[j].v]) % 3 != stps[j].d)71                     {72                         ok[i] = j + 1;73                         break;74                     }75                 }76             }77         }78         int cnt = 0,rline=0,judgeperson=0;79         for (int i = 0; i < n; i++)80         {81             if (ok[i]== 0)82             {83                 cnt++;84                 judgeperson = i;85             }86             if (ok[i] > rline) rline = ok[i];87         }88         if (cnt == 0)printf("Impossible\n");89         else if (cnt == 1)printf("Player %d can be determined to be the judge after %d lines\n",judgeperson,rline);90         else printf("Can not determine\n");91     }92     return 0;93 }
      

12、hdu 1272 小希的迷宫

　　题意：如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。

　　思路：并查集。

1 #include
      
        2 using namespace std; 3 const int maxn = 100010; 4 int pre[maxn]; 5 bool vis[maxn]; 6 int Find(int x) 7 { 8     if (pre[x] == x)return x; 9     else10     {11         int fa = pre[x];12         pre[x] = Find(fa);13         return pre[x];14     }15 }16 17 bool Union(int x, int y)18 {19     int fx = Find(x), fy = Find(y);20     if (fx == fy)return true;21     else22     {23         pre[fx] = fy;24         return false;25     }26 }27 int main()28 {29     int u, v;30     while (~scanf("%d%d", &u, &v))31     {32         if (u == -1 && v == -1)break;33         if (u == 0 && v == 0)34         {35             printf("Yes\n");36             continue;37         }38         for (int i = 0; i < maxn; i++)pre[i] = i;39         bool flag = true;40         do41         {42             if (!flag)continue;43             if (Union(u, v))44             {45                 flag = false;46             }47         } while (scanf("%d%d", &u, &v) && u != 0 && v != 0);48         if (!flag) printf("No\n");49         else50         {51             memset(vis, 0, sizeof(vis));52             int cnt = 0;53             for (int i = 0; i < maxn; i++)54             {55                 if (pre[i] == i)continue;56                 int f = Find(i);57                 if (!vis[f])58                 {59                     cnt++;60                     vis[f] = true;61                 }62             }63             if (cnt == 1) printf("Yes\n");//只能有一个连通块64             else printf("No\n");65         }66     }67     return 0;68 }
      

13、poj 1308 Is It A Tree

　　题意：输入数据表示存在父子节点关系的点的编号，判断是否为树。

　　思路：并查集。

1 #include
      
        2 using namespace std; 3 const int maxn = 100010; 4 int pre[maxn]; 5 bool vis[maxn]; 6 int Find(int x) 7 { 8     if (pre[x] == x)return x; 9     else10     {11         int fa = pre[x];12         pre[x] = Find(fa);13         return pre[x];14     }15 }16 17 bool Union(int x, int y)18 {19     int fx = Find(x), fy = Find(y);20     if (fx == fy)return true;21     else22     {23         pre[fx] = fy;24         return false;25     }26 }27 int main()28 {29     int u, v;30     int Case = 1;31     while (~scanf("%d%d", &u, &v))32     {33         if (u<0 && v <0)break;34         if (u == 0 && v == 0)35         {36             printf("Case %d is a tree.\n",Case++);37             continue;38         }39         for (int i = 0; i < maxn; i++)pre[i] = i;40         bool flag = true;41         do42         {43             if (!flag)continue;44             if (Union(u, v))45             {46                 flag = false;47             }48         } while (scanf("%d%d", &u, &v) && u != 0 && v != 0);49         if (!flag) printf("Case %d is not a tree.\n",Case++);50         else51         {52             memset(vis, 0, sizeof(vis));53             int cnt = 0;54             for (int i = 0; i < maxn; i++)55             {56                 if (pre[i] == i)continue;57                 int f = Find(i);58                 if (!vis[f])59                 {60                     cnt++;61                     vis[f] = true;62                 }63             }64             if (cnt == 1) printf("Case %d is a tree.\n", Case++);//只能有一个连通块65             else printf("Case %d is not a tree.\n",Case++);66         }67     }68     return 0;69 }
      

 14、LA 3644 X-Plosives

　　题意：给出若干对，表示a和b相连，要保证每个连通块为一颗树，要删去哪些对。

　　思路：并查集。

1 #include
      
        2 using namespace std; 3 const int maxn = 100100; 4 int pre[maxn]; 5 int Find(int x) 6 { 7     if (x == pre[x]) return x; 8     else 9     {10         int fa = pre[x];11         pre[x] = Find(fa);12         return pre[x];13     }14 }15 bool Union(int x, int y)16 {17     int fx = Find(x), fy = Find(y);18     if (fx == fy) return true;19     else20     {21         pre[fx] = fy;22         return false;23     }24 }25 int main()26 {27     int a,b;28     while (~scanf("%d", &a))29     {30         scanf("%d", &b);31         for (int i = 0; i < maxn; i++) pre[i] = i;32         Union(a, b);33         int cnt = 0;34         while (scanf("%d", &a) && a != -1)35         {36             scanf("%d", &b);37             if (Union(a, b)) cnt++;38         }39         printf("%d\n", cnt);40     }41     return 0;42 }
      

 15、LA 3027 Corporative Network

　　题意：每次可以询问一家公司到其所在的群的中心公司的线路长度，或者将某个群的中心公司A接到另一个群的某家公司B，并且两个群所有的公司的中心改为原来B所在群的中心公司。

　　思路：带权并查集。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn = 20010; 6 int pre[maxn]; 7 int val[maxn]; 8 int n; 9 void Init()10 {11     for (int i = 0; i <= n; i++) pre[i] = i, val[i] = 0;12 }13 int Find(int x)14 {15     if (x == pre[x]) return x;16     else17     {18         int fa = pre[x];19         pre[x] = Find(fa);20         val[x] = val[x] + val[fa];21         return pre[x];22     }23 }24 bool Union(int x, int y,int l)25 {
    //I x y26     int fx = Find(x), fy = Find(y);27     if (fx == fy) return true;28     else29     {30         pre[fx] = fy;31         val[fx] = l + val[y];32         return false;33     }34 }35 int main()36 {37     int t;38     scanf("%d", &t);39     char s[5];40     while (t--)41     {42         scanf("%d", &n);43         Init();44         while (~scanf("%s", s))45         {46             if (s[0] == 'O')break;47             if (s[0] == 'E')48             {49                 int x;50                 scanf("%d", &x);51                 Find(x);52                 printf("%d\n", val[x]);53             }54             else55             {56                 int x, y;57                 scanf("%d%d", &x, &y);58                 Union(x, y, abs(x - y) % 1000);59             }60         }61     }62     return 0;63 }
        
       
      

 16、LA 4487 Exclusive-OR

　　题意：每次告诉你A的值是多少或者A和B异或的结果是多少，或者询问k个数连续异或的值。

　　思路：带权并查集。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 const int maxn = 21000;  6 int pre[maxn], re[maxn];  7 int vis[maxn], num[20];  8 int supperroot = maxn - 10;  9 void init(int n) 10 { 11     for (int i = 0; i <= n + 1; i++) 12     { 13         pre[i] = i; 14         re[i] = 0; 15         vis[i] = 0; 16     } 17     pre[supperroot] = supperroot; 18     re[supperroot] = 0; 19 } 20 int Find(int x) 21 { 22     if (x != pre[x]) 23     { 24         int fa = pre[x]; 25         pre[x] = Find(pre[x]); 26         re[x] ^= re[fa]; 27     } 28     return pre[x]; 29 } 30 bool Union(int x, int y, int val) 31 { 32     int fx = Find(x); 33     int fy = Find(y); 34     if (fx == fy) 35     { 36         if ((re[x] ^ re[y]) != val) return 0; 37         else return 1; 38     } 39     if (fx == supperroot) swap(fx, fy); 40     pre[fx] = fy; 41     re[fx] = re[x] ^ re[y] ^ val; 42     return 1; 43 } 44 int main() 45 { 46     int n, Q, p, q, val, kase = 0; 47     char ch[2]; 48     char s[40]; 49     while (scanf("%d%d", &n, &Q)) 50     { 51         if (n==0&&Q==0) break; 52         init(n); 53         printf("Case %d:\n", ++kase); 54         bool flag = 0; 55         int facts = 0; 56         for (int i = 1; i <= Q; i++) 57         { 58             scanf("%s", ch); 59             if (ch[0] == 'I') 60             { 61                 facts++; 62                 gets(s); 63                 if (sscanf(s, "%d%d%d", &p, &q, &val) == 2) 64                 { 65                     val = q;  66                     q = supperroot; 67                 } 68                 if (flag) continue; 69                 if (!Union(p, q, val)) 70                 { 71                     printf("The first %d facts are conflicting.\n", facts); 72                     flag = 1; 73                 } 74             } 75             else 76             { 77                 int k, ans = 0; 78                 scanf("%d", &k); 79                 for (int i = 1; i <= k; i++) 80                 { 81                     scanf("%d", &num[i]); 82                     if (flag) continue; 83                     int fa = Find(num[i]); 84                     ans ^= re[num[i]]; 85                     num[i] = fa; 86                     vis[fa] ^= 1; 87                 } 88                 if (flag) continue; 89                 bool unknow = false; 90                 for (int i = 1; i <= k; i++) 91                 { 92                     if (vis[num[i]]) 93                     { 94                         if (num[i] != supperroot) 95                         { 96                             unknow = true; 97                         } 98                         vis[num[i]] = 0; 99                     }100                 }101                 if (!unknow) printf("%d\n", ans);102                 else printf("I don't know.\n");103             }104         }105         printf("\n");106     }107     return 0;108 }
        
       
      

 17、uva 11987 Almost Union-Find

　　题意：第一种操作为把P和Q所在集合和并，第二种为把结点P放到Q所在集合里，第三种是查询P所在集合的元素数目和总和。

　　思路：带权并查集。初始时把每个结点的祖先指向i+n,这样当第二种操作时，就不会影响P原来集合的根。

1 #include
      
        2 using namespace std; 3 const int maxn = 100100; 4 int pre[maxn]; 5 int sum[maxn]; 6 int cnt[maxn]; 7 int n, m; 8 int Find(int x) 9 {10     if (x == pre[x]) return x;11     else12     {13         int fa = pre[x];14         pre[x] = Find(fa);15         return pre[x];16     }17 }18 void Union(int x, int y)19 {20     int fx = Find(x), fy = Find(y);21     if (fx != fy)22     {23         pre[fx] = fy;24         sum[fy] += sum[fx];25         cnt[fy] += cnt[fx];26         sum[fx] = 0;27         cnt[fx] = 0;28     }29 }30 void Change(int x, int to)31 {32     int f = Find(to);33     int init = Find(x);34     pre[x] = f;35     sum[f] += x, cnt[f]++;36     sum[init] -= x, cnt[init]--;37 }38 int main()39 {40     while (~scanf("%d%d", &n, &m))41     {42         for (int i = 0; i <= n; i++) pre[i] = i+n, cnt[i+n] = 1, sum[i+n] = i,pre[i+n]=i+n;43         int s;44         while (m--)45         {46             scanf("%d", &s);47             if (s == 1)48             {49                 int p, q;50                 scanf("%d%d", &p, &q);51                 Union(p, q);52             }53             else if (s == 2)54             {55                 int p, q;56                 scanf("%d%d", &p, &q);57                 Change(p, q);58             }59             else60             {61                 int p;62                 scanf("%d", &p);63                 printf("%d %d\n", cnt[Find(p)], sum[Find(p)]);64             }65         }66     }67     return 0;68 }
      

 18、LA 5898/uva 1493/hdu 4056 Draw a Mess

　　题意：有若干个人按照顺序在n*m的黑板上画4种图形。求最后各种颜色所占的像素数目。

　　思路：用并查集维护每行当前位置的下一个可以画的位置，然后倒序更新。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7  8 const int maxn = 205; 9 const int maxm=100500;10 char str[maxm][25];11 int xx[maxm], yy[maxm], p[maxm], t[maxm], c[maxm];12 int Next[maxn][maxm];13 int Find(int i, int t)14 {15     if (Next[i][t] != t)16         Next[i][t] = Find(i, Next[i][t]);17     return Next[i][t];18 }19 int dele(int i, int l, int r)20 {21     int ret = 0;22     l = Find(i, l);23     while (l <= r)24     {25         ret++;26         Next[i][l] = l + 1;27         l = Find(i, l);28     }29     return ret;30 }31 int main()32 {33     int n, m, q;34     int i, j, x, y, r, w, l, h, color;35     int tmp1, tmp2, tmp3;36     int ans[10];37     while (~scanf("%d%d%d", &n, &m, &q))38     {39         for (i = 0; i
           
            = 0; i--)55 {56 x = xx[i], y = yy[i];57 if (str[i][0] == 'D')58 { //菱形59 r = p[i], color = c[i];60 for (j = max(0, x - r); j <= min(n - 1, x + r); j++)//枚举行61 ans[color] += dele(j, max(0, y - r + abs(x - j)),min(m - 1, y + r - abs(x - j)));62 }63 else if (str[i][0] == 'T')64 { //等腰三角形65 w = p[i], color = c[i];66 h = (w + 1) / 2;67 for (j = max(0, x); j
            
              1) printf(" ");89 printf("%d", ans[i]);90 }91 printf("\n");92 }93 return 0;94 }
            
           
          
         
        
       
      

 19、OpenJ_POJ - C15C  Rabbit's Festival

　　题意：每个结点都住着一只兔子，一共有n个结点，有m条无向边，每条边在第ci天时无法通行。问从1~k天中，每天可以两两相遇的兔子的对数？

　　思路：某一天可以相遇，则在同一个并查集当中，易得对数。怎么维护这个并查集呢？CDQ分治。参考：

 

1 //CDQ分治+并查集  2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 const int maxn = 100010;  7 const int maxe = 200010;  8 struct edge  9 { 10     int from, to,next; 11     edge(int ff=0,int tt=0,int nn=0):from(ff),to(tt),next(nn){} 12 }Edge[maxe]; 13 int Head[maxn], totedge; 14 int pre[maxn], cnt[maxn];//其父结点、以其为根的树的结点个数 15 int n, m, k; 16 void addedge(int from, int to, int c) 17 { 18     Edge[totedge] = edge(from, to, Head[c]); 19     Head[c] = totedge++; 20 } 21 void init() 22 { 23     for (int i = 1; i <= n; i++) pre[i] = i, cnt[i] = 1; 24     memset(Head, -1, sizeof(Head)); 25     totedge = 0; 26 } 27 int find(int x) 28 {
    //找到根结点，不用路径压缩 29     while (pre[x] != x) 30     { 31         x = pre[x]; 32     } 33     return x; 34 } 35 long long Cal(int x) 36 {
    //以x为根的所有结点可以形成的配对对数 37     return 1ll * x*(x - 1) / 2; 38 } 39 struct CDQ 40 { 41     long long result; 42     pair
         
           stk[maxe];//保存最近添加的边，方便从并查集删去 43     int stkTop; 44     void Push(edge&cur) 45     {
    //将边cur加入并查集 46         int a = find(cur.from); 47         int b = find(cur.to); 48         if (a == b) return; 49         result -= Cal(cnt[a]); 50         result -= Cal(cnt[b]); 51         if (cnt[a] > cnt[b]) swap(a, b); 52         cnt[b] += cnt[a]; 53         pre[a] = b; 54         result += Cal(cnt[b]); 55  56         stk[++stkTop] = make_pair(a, b); 57     } 58     void Push(int l, int r) 59     {
    //从l~r天所有不可通的道路加入并查集（即当前遍历的天数不在l~r中） 60         for (int i = l; i <= r; i++) 61         { 62             for (int j = Head[i]; j != -1; j = Edge[j].next) 63             { 64                 Push(Edge[j]); 65             } 66         } 67     } 68     void Pop(int l, int r) 69     { 70         for (int i = r; i >= l; i--) 71         { 72             int u = stk[i].first; 73             int v = stk[i].second; 74             result -= Cal(cnt[v]); 75             cnt[v] -= cnt[u]; 76             result += Cal(cnt[u]); 77             result += Cal(cnt[v]); 78             pre[u] = u; 79         } 80     } 81  82     void cdq(int l, int r) 83     {
    //将从l~r天可以连通的道路加入并查集，不可连通的则从并查集删去 84         if (l == r) 85         {
    //如果刚好第l天没有连通的道路不在并查集中 86             printf("%lld\n", result); 87             return; 88         } 89         int mid = (l + r) >> 1; 90         int tmp = stkTop; 91         Push(mid + 1, r);//考虑l~mid天，将第mid+1~r天不可连通的道路加入并查集 92         cdq(l, mid); 93         Pop(tmp + 1, stkTop);//把加入的边删去 94         stkTop = tmp; 95         Push(l,mid);//考虑mid+1~r天，将第l~mid天不可连通的道路加入并查集 96         cdq(mid + 1, r); 97         Pop(tmp + 1, stkTop); 98         stkTop = tmp; 99     }100     void cdqinit()101     {102         stkTop = -1;103         result = 0;104     }105     void Run()106     {107         cdq(1, k);108     }109 }CDQ;110 int main()111 {112     while (~scanf("%d%d%d", &n, &m, &k))113     {114         init();115         CDQ.cdqinit();116         for (int i = 1; i <= m; i++)117         {118             int u, v, c;119             scanf("%d%d%d", &u, &v, &c);120             if (c <= k)121             {
    //如果1~k中有某一天不通，则加到对应边中122                 addedge(u, v, c);123                 continue;124             }125             //将从1~k天都能连通的路直接连起来126             edge tmp = edge(u, v, 0);127             CDQ.Push(tmp);128         }129         CDQ.Run();130     }131     return 0;132 }