求帮忙,按照刘汝佳的模板编的,wa7

P3367 【模板】并查集

samsara_1 @ 2017-06-07 13:46:24

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int p[10005];

int find(int t)
{
    return p[t] == t ? t : p[t] = find(p[t]); 
}

int main()
{
    int i,j,k,m,n,z,x,y;
    cin >> n >> m;
    for(i = 1; i <= 10000; i++)
        p[i] = i;
    for(i = 1; i <= m; i++)
    {
        cin >> z >> x >> y;
        if(z == 1)
        {
            if(find(x) != find(y))
                p[y] = x;
        }
        else
        {
            if(find(x) == find(y))
                cout << "Y";
            else
                cout << "N";
            cout << endl;
        }
    }

    return 0;
}

by pb0207 @ 2017-06-07 15:58:43

@ 孟昭旭 进行合并操作时,为了保证复杂度,需要把p[y]=x,改为p[find(y)]=find(x)比较好。


by fanta2017 @ 2017-06-07 17:59:58

感谢,一语点醒我,让我少调2小时程序(^_^)


by JamesHen @ 2017-06-25 15:26:25

不是保证复杂度,上面那位仁兄的问题是把y并到x的集合去了,题目是合并两个集合。。。

@pb0207


by as2393125 @ 2017-08-04 21:52:58

二者没区别。

@ JamesHen


|