P1111 修复公路 并查集简单应用

· · 个人记录

P1111 修复公路

注意！

把某个两个点合并一定是用连通块祖宗去合并而不是建立两个节点的父子关系（不能写成"f[e[i].v]=e[i].u;"，这样达不到合并连通块所有节点的效果）

//P1111 修复公路
//连通块数初始为点数，并查集维护当前连通块，按时间对道路排序
//每次合并道路两端点所在的连通块，如果可合并（不在同一连通块内）就合并、把连通块数量减1
//连通块数量为1时所有点连通，此时的t就是答案 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2010,M=100010;
int f[N],n,m,x,y,t;
struct Edge
{int a,b,t;}e[M];
bool cmp(Edge x,Edge y)
{
    return x.t<y.t;
}
int find(int x)
{
    if(x!=f[x]) return f[x]=find(f[x]);
    else return x;//这里不return开了O2就会MLE 
} 
int main()
{
    scanf("%d%d",&n,&m);
    int cnt=n;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].t);
        f[e[i].a]=e[i].a,f[e[i].b]=e[i].b;
    }
    sort(e+1,e+1+m,cmp);
    bool flag=0;
    for(int i=1;i<=m;i++)
    {
        int fx=find(e[i].a),fy=find(e[i].b);
        if(fx!=fy) f[fx]=fy,cnt--;
        if(!flag&&cnt==1) printf("%d",e[i].t),flag=1;
    }
    if(flag==0) printf("-1");
    return 0;
}