Kruskal，怎么判断是非连通图

zhuyuhao1123 @ 2024-10-09 22:24:17

#include<bits/stdc++.h>
#define M 2147483647
using namespace std;
struct node
{
    int u,v,w;
}a[200001];
int f[5001],n,m,ans;
bool b[5001];
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
inline int findfather(int x)
{
    if(f[x]==x) return x;
    return f[x]=findfather(f[x]);
}
inline bool cmp(node x,node y)
{
    return x.w<y.w;
}
void kruskal()
{
    int sum=0;
    sort(a+1,a+m+1,cmp);
    for(register int i=1;i<=m;++i)
    {
        int fu=findfather(a[i].u),fv=findfather(a[i].v);
        if(fu==fv) continue;
        ans+=a[i].w,f[fu]=fv;
        if(++sum==n-1) break;
    }
}
int main()
{
    n=read(),m=read();
    for(register int i=1;i<=n;++i) f[i]=i;
    for(register int i=1;i<=m;++i)
    a[i].u=read(),a[i].v=read(),a[i].w=read();
    kruskal();
    printf("%d\n",ans);
    return 0;
}

by aeiouaoeiu @ 2024-10-09 22:28:01

@zhuyuhao1123 使用并查集即可

by Lisuyang @ 2024-10-09 22:29:03

记录总共经过了多少个点

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 6, M = 2e5 + 6; 
int n, m, ds[N], ans, num;
struct edge{int x, y, z;}e[M<<1];
int find(int x){return ds[x] < 0 ? x : ds[x] = find(ds[x]);}
bool mst(){
    for(int i = 1; i <= m<<1; ++ i){
        if(num == n-1) break;
        int x = find(e[i].x), y = find(e[i].y);
        if(x == y) continue;
        ds[x] = y, ans += e[i].z, num ++;
    }
    if(num == n-1) return 1;
    return 0;
}
int main(){
    memset(ds, -1, sizeof ds);
    scanf("%d%d", &n, &m);
    for(int i = 1, x, y, z; i <= m; ++ i)
        scanf("%d%d%d", &x, &y, &z), e[i<<1] = {x, y, z}, e[i<<1|1] = {y, x, z};
    sort(e+1, e+1+m*2, [](edge x, edge y){return x.z < y.z;});
    if(mst()) printf("%d", ans);
    else printf("orz");
    return 0;
}

@zhuyuhao1123

by aeiouaoeiu @ 2024-10-09 22:29:38

如果最后能够找到不止一个满足 findfather(i)==i 的 i，那么就无法连成一棵树

by Jean_Gunnhildr @ 2024-10-09 22:30:45

@zhuyuhao1123 把sum改为全局变量，print输出改为：

(sum==n-1)?cout<<ans:cout<<"orz";

就行了，因为如果不连通，连不到 n-1 条边

求关

by zhuyuhao1123 @ 2024-10-09 22:34:52

@Alicezhou 已关

by rb_tree @ 2024-10-12 20:21:40

跑一遍最短路，看看有没有最短路长度仍是无穷大的

by dami826 @ 2024-10-25 08:42:10

并查集每次合并都取编号较小的，最后看有没有节点的 father[i]!=1