厌氧代码求调

1_1_1_1_1_1_ @ 2023-08-26 11:02:49

#include<bits/stdc++.h>

using namespace std;

int n, m;

int p[10001];

int find(int t)
{
    int y;

    y = p[t];
    while(p[y] != y)
    {
        y = p[y];
    }
    return(y);
}

void Union(int x, int y)
{
    int f1, f2;

    f1 = find(x);
    f2 = find(y);
    p[f1] = f2;
}

int main()
{
    int i;
    int num;
    int x, y;
    int f1, f2;

    cin >> n >> m;
    for(i = 1; i <= n; i++)
    {
        p[i] = i;
    }
    for(i = 0; i < m; i++)
    {
        cin >> num >> x >> y;
        if(num == 2)
        {
            f1 = find(x);
            f2 = find(y);
            if(f1 == f2)
            {
                cout << 'Y';
            }
            else
            {
                cout << 'N';
            }
            cout << endl;
        }
        else
        {
            Union(x, y);
        }
    }
}

by Bingxiu @ 2023-08-26 11:07:43

@1_1_1_1_11 这能不超吗，一个链就死了，要路径压缩（）

by Yuzilihhh @ 2023-08-26 11:08:33

@1_1_1_1_11 把find改成路径优化即可，如：

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

by 1_1_1_1_1_1_ @ 2023-08-26 11:16:22

@Yuzilihhh 过了谢谢

by chengpengjin0908 @ 2023-08-27 19:58:03

咱就是说，这样不更好吗？

#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[10001];
int find(int t)
{
    if(p[t]==t)
        return t;
    return p[t]=find(p[t]);
}
void Union(int x, int y)
{
    int f1,f2;
    f1=find(x);
    f2=find(y);
    p[f1]=f2;
}
int main()
{
    int i;
    int num;
    int x,y;
    int f1,f2;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        p[i]=i;
    for(i=0;i<m;i++)
    {
        cin>>num>>x>>y;
        if(num==1)
            p[find(x)]=find(y);
        else
        {
            if(find(x)==find(y))
                cout<<"Y"<<endl;
            else
                cout<<"N"<<endl;
        }
    }
    return 0;
}

by chengpengjin0908 @ 2023-08-27 19:59:05

狗头保命！！！ 大佬不喜勿喷！！！