2020.4.11普及C组 Wormhole Sort【纪中】【并查集】

并查集

我们首先做并查集的普通操作：把自己当作自己的父亲。
其次我们枚举输入的点，如果不是同一个父亲就合并，
并记录当前的黑洞的宽度。
那怎么实现？

//其实这也是一个并查集的基本操作，很容易理解
xx=find(b[i].x);
yy=find(b[i].y);
if(xx!=yy)
 {
    f[xx]=yy;
    ans=b[i].z;
 }

当然，我们还需要一个$while$循环，
用来求出每一个奶牛是否都到达了自己的位置，怎么求？
我们可以设一个$js$变量，遇到到达了自己的位置的就++，
当$js=n-1$,就表示全部都归位了。

$ACCode$

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,a[100010],f[100010];
int js,xx,yy,ans=-1;
struct node
{
    int x,y,z;
}b[100010];
bool cmp(const node&l,const node&r)
{
    return l.z>r.z;
}
int find(int x)
{
    if(f[x]==x)
        return f[x];
    return f[x]=find(f[x]);
}
int main()
{
	freopen("wormsort.in","r",stdin);
	freopen("wormsort.out","w",stdout);
	cin>>n>>m;
    for(int i=1; i<=n; i++)
       scanf("%d",&a[i]);
    for(int i=1; i<=m; i++)
       scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
    sort(b+1,b+m+1,cmp);
    for(int i=1; i<=n; i++) 
	   f[i]=i;
    for(int i=1; i<=m; i++)
     {
        while(find(js)==find(a[js])) //求出每一个奶牛是否都到达了自己的位置
         {
            js++;
            if(js==n-1)
             {
                cout<<ans;
                return 0;
             }
         }
        xx=find(b[i].x);  
        yy=find(b[i].y);
        if(xx!=yy) //不是同一个父亲，合并！记录！
         {
            f[xx]=yy;
            ans=b[i].z;
         }
     }
    cout<<ans;
    return 0;
}