poj-1182 种类并查集

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/42874641

转： 用0 1 2 分别表示A B C的关系。

0吃1,1吃2,2吃0.

注意这个编号都是以根结点为参照的，不是绝对的。

开一个val数组，一开始这个数组为0，所有的点都是独立的，不是相连的，没有关系。

慢慢加入点之后，把有关系的合并在一起，并且编号的相对大小确定一个集合中的关系。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <iomanip>

using namespace std;

int n, k, d, x, y;
int fa[50010];
int rankk[50010];
int ans;

int findd(int x)
{
    if (fa[x] == -1)
        return x;

    int tmp = findd(fa[x]);

    rankk[x] += rankk[fa[x]];
    rankk[x] %= 3;

    return fa[x] = tmp;
}

int main()
{
    scanf("%d %d",&n,&k);
    {

        memset(fa,-1,sizeof(fa));
        memset(rankk,0,sizeof(rankk));

        ans = 0;

        while (k--)
        {
            scanf("%d %d %d", &d, &x, &y);

            if (x > n || y > n)
            {
                ans++;
                continue;
            }

            int fx = findd(x);
            int fy = findd(y);

            if (fx == fy)
            {
                if (d == 1 && rankk[x] != rankk[y])
                    ans++;
                if (d == 2 && (rankk[x] + 1) % 3 != rankk[y])
                    ans++;
            }
            else
            {
                if (d == 1)
                {
                    fa[fy] = fx;
                    rankk[fy] = rankk[x] - rankk[y];
                    rankk[fy] = (rankk[fy] + 3) % 3;
                }
                else
                {
                    fa[fy] = fx;
                    rankk[fy] = rankk[x] - rankk[y] + 1; 
                    rankk[fy] = (rankk[fy] + 3) % 3;
                }

            }
        }
        printf("%d\n",ans);
    }
    return 0;
}