Poj(1703),种类并查集

已经不是第一次接触种类并查集了，直到今天才搞懂。

感谢红黑联盟，感谢杰哥！！！

每个节点只要关系确定，不管是不是同一个集合里面，都把他们放到一个集合里面，用一个rank[]数组记录他们与根节点的关系，比较神奇的地方有两处：

1、find函数里面,因为find是递归写的，不断往上找，不断更新rank[x](与根节点的关系)，这个%k，也是很牛逼的，2种类型，标号只有01；

2、Union函数里面，更新rank[fy],rank[y]这里是(rank[x] - rank[y] +T)%2,这里特值法证明一下吧，我智商已经不够用了，比如说，新的节点0，合并后，就往上找，比如说找到了110,这个点肯定不是跟根同一个集合，0-A,0-B,然后(0-0+1)%2==1;

啊哈，特例搞一下吧，脑容量不够了。

#include<cstdio>

const int N = ;

int n, m, f[N], rank[N];

void init()

{

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

        f[i]=i,rank[i]=;

}

int find(int x)

{

    if(x==f[x])

        return f[x];

    int fa=f[x];

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

    rank[x] = (rank[x]+rank[fa])%;

    return f[x];

}

bool Union(int x,int y)

{

    int fx=find(x), fy=find(y);

    if(fx==fy) return false;

    f[fy] = fx;

    rank[fy] = (rank[x]-rank[y]+)%;

}

int main()

{

    int T,a,b,fa,fb;

    char ch;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%*c",&n,&m);

        init();

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

        {

            scanf("%c%d%d%*c",&ch,&a,&b);

            if(ch=='D')

            {

                Union(a,b);

            }

            else

            {

                fa = find(a), fb=find(b);

                if(fa==fb)

                {

                    if(rank[a]==rank[b]) puts("In the same gang.");

                    else puts("In different gangs.");

                }

                else

                    puts("Not sure yet.");

            }

        }

    }

    return ;

}

巴特西

Poj(1703),种类并查集

最新文章

热门文章