求大神帮查问题,MLE,多次无语

P3367 【模板】并查集

Wenchih @ 2018-10-30 21:39:39

#include<bits/stdc++.h>

using namespace std;

int N,M;

int ys[100001];
int zi,xi,yi;

void gb(int xx,int yy)// 合并
{
    if(ys[xx] == ys[yy])
    {
        return;
    }
    for (int i = ys[yy];;i = ys[i])
    {
        if(i == ys[i])
        {
            ys[i] = ys[xx];
            break;
        }
        ys[i] = ys[xx];
    }
}

int find(int xx)
{
    if(xx == ys[xx])
    {
        return xx;
    }
    else 
    {
        return ys[xx] = find(ys[xx]);
    }
}

int main()
{
    cin.sync_with_stdio(false);
    cout.tie(0);
    freopen("test.in","r",stdin);

    cin >> N >> M;
    for (int i = 1;i <= N; i ++)
    {
        ys[i] = i;
    }

    for (int i = 1;i <= M; i++)
    {
        cin >> zi;
        cin >> xi >> yi;
        if(zi == 1)
        {
            gb(xi,yi);
        }
        else if(zi == 2)
        {
            if(find(xi) == find(yi))
            {
                cout << 'Y' << '\n';
            }
            else cout << 'N' << '\n';

        }
    }

    return 0;
}

by 7KByte @ 2018-10-30 21:44:50

合并的时候是把x的root接到y的root上吧,不是直接把x接到y上吧


by Southern_way @ 2018-10-30 21:46:54

数组只要开10000吧


by Wenchih @ 2018-10-30 21:50:35

@雄英天下第一 10000也过不了


by Wenchih @ 2018-10-30 21:51:35

@Gang_Leader ys数组就是root,我都把yy的root合并到xx上了


by Southern_way @ 2018-10-30 21:53:57

@Wenchih freopen,你是认真的吗


by Southern_way @ 2018-10-30 21:54:41

@Wenchih 合并错了


by Southern_way @ 2018-10-30 21:55:21

int z,x,y;
        cin >> z >> x >> y;
        if (z == 1){
            f[find(x)] = find(y);
        } 
        else if (z == 2){
            if (find(x) == find(y)) cout << "Y" << endl;
            else cout << "N" << endl;
        }

by Southern_way @ 2018-10-30 21:58:23

应该让一个的祖先成为另一个的祖先的父亲


by Wenchih @ 2018-10-30 21:58:49

@雄英天下第一 还没提交,freopen未注释


by Southern_way @ 2018-10-30 21:59:03

找祖先的过程中顺便路压


| 下一页