POJ_1703 Find them, Catch them 【并查集】

一、题面

POJ1703

二、分析

需要将并查集与矢量法则相结合。par数组用以记录父节点，rank用以记录与父节点的关系。如题意，有两种关系，设定0是属于同一个帮派，1表示不属于同一个帮派。

运用并查集的时候判断x，y时考虑几种情况：

1.x与y父节点不相同：此时为不清楚两者关系。

2.x与y父节点相同，rank的值也相同：两者属于同一帮派。

3.x与y父节点相同，rank的值不相同：两者不属于同一帮派。

要得到这个关系，需要在并查集的find函数内对各个点的rank和par的值进行不断的更新。

对于rank，需要使用矢量加法，如

$\overrightarrow{AB}+\overrightarrow {BC}=\overrightarrow {AC}$

结合题目就是例：x的父节点px，如果x与父节点的关系是rank[x]，px与父节点的关系是rank[px],那么x与par[px]的关系就是

$(rank[x] + rank[px])\%2$

其他的推理类似。

在find的路径压缩时，注意把rank关系进行更新即可，在union时涉及到x,y与它们的父节点px,py的rank值更新，其实原理相同。

三、AC代码

 #include <cstdio>

 #include <iostream>

 #include <fstream>

 using namespace std;

 const int MAXN = 1e5+;

 int par[MAXN];

 int Rank[MAXN];

 void init()

 {

     for(int i = ; i < MAXN; i++)

     {

         par[i] = i;

         Rank[i] = ;

     }

 }

 int find(int x)

 {

     if(par[x] == x)

         return x;

     int px = par[x];

     par[x] = find(par[x]);

     Rank[x] = (Rank[px]+Rank[x])%;

     return par[x];

 }

 void Union(int x, int y)

 {

     int px = find(x);

     int py = find(y);

     if(px == py)

         return;

     par[px] = py;

     Rank[px] = (Rank[x]++Rank[y])%;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

     int T, M, N, x, y;

     char op;

     while(scanf("%d", &T)!=EOF)

     {

         while(T--)

         {

             init();

             scanf("%d %d", &N, &M);

             for(int i = ; i < M; i++)

             {

                 getchar();

                 scanf("%c %d %d", &op, &x, &y);

                 if(op == 'A')

                 {

                     int px = find(x);

                     int py = find(y);

                     if(px != py)

                     {

                         puts("Not sure yet.");

                     }

                     else

                     {

                         if(Rank[x] == Rank[y])

                             puts("In the same gang.");

                         else

                             puts("In different gangs.");

                     }

                 }

                 else

                 {

                     Union(x, y);

                 }

             }

         }

     }

     return ;

 }

巴特西

POJ_1703 Find them, Catch them 【并查集】

一、题面

二、分析

三、AC代码

最新文章

热门文章