T了三个点,如何优化?

P3367 【模板】并查集

geray_king @ 2019-03-03 21:19:48

T了2 9 10 三个点,怎么破

#include<bits/stdc++.h>
using namespace std;
int f[10010];
int n,m;
int find_father(int x)
{
    if(f[x]==x)return x;
    return find_father(f[x]);
}
/*void Union(int x,int y)
{
    int a1=find_father(x);
    int b=find_father(y);
    if(a1!=b)
    f[b]=f[a1];
}*/
int main()
{   cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for(int i=0;i<m;i++)
    {   int a,s,d;
        cin>>a>>s>>d;
        if(a==1)
        {
        f[find_father(s)]=find_father(d);
        }
        if(a==2)
        {
            if(find_father(s)==find_father(d))
            printf("Y\n");
            else 
            printf("N\n");
        }
    }
    return 0;
 } 

by geray_king @ 2019-03-03 21:52:05

@Neptune_Disaster ···啥意思?


by Catalan1906 @ 2019-03-03 21:52:57

@geray_king 是在问对话啥意思还是按秩合并啥意思?


by geray_king @ 2019-03-03 21:56:25

@Neptune_Disaster 按秩合并


by Catalan1906 @ 2019-03-03 21:59:27

@geray_king 按秩合并就是按秩序合并

并查集是模拟一棵树

可以按照树高合并,同时要维护树高

可以优化到log级别


上一页 |