如何判断图是否联通？

George_qwe @ 2024-03-31 17:11:54

by OldDriverTree @ 2024-03-31 17:13:23

@George_qwe dfs 一遍，或者判断 kruskal 结束后加入的边数是否位 n-1

by _QyGyQ_ @ 2024-03-31 17:19:41

并查集

by George_qwe @ 2024-03-31 17:43:06

@OldDriverTree 用Prim+链式前向星就只能用dfs吗？

by OldDriverTree @ 2024-03-31 17:44:19

@George_qwe 不是，判断选择的点 dis 是否为正无穷

by George_qwe @ 2024-03-31 17:47:45

@OldDriverTree 是Prim结束后判断吗？

by George_qwe @ 2024-03-31 17:48:23

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int M=2e5+5;
const int N=5e3+5;
const int inf=0x7fffffff;
ll n,m,cnt,ans=0,tot,now=1;
ll size[M],head[M];
ll dis[N],vis[N];
struct Edge{
    ll w,to,next;
}edge[2*M];//边集 
inline int read()
{
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
void add(int x,int y,int z){
    cnt++;//边的编号, 1~n 
    edge[cnt].to=y;
    edge[cnt].next=head[x];//next 存上一条边的编号
    edge[cnt].w=z;
    head[x]=cnt;
}

void init()
{
    n=read(),m=read();
    for(int i=1,u,v,w;i<=m;++i)
    {
        u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);//双向边 
    }
}
void print(){
    for(int i=1;i<=n;i++){
        cout<<i<<endl;
        for(int j=head[i];j!=-1;j=edge[j].next){
            cout<<i<<" "<<j<<" "<<edge[j].to<<" "<<edge[j].w<<endl;
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        cout<<head[i]<<" ";
    }
}
int prim(){
    for(int i=2;i<=n;i++){dis[i]=inf;   }
    for(int j=head[1];j!=-1;j=edge[j].next){
        dis[edge[j].to]=min(dis[edge[j].to] , edge[j].w);
    }
    while(tot<n-1){
        ++tot;
        int minn=inf;
        vis[now]=1;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&minn>dis[i]){//找出连上的边的最小边 
                minn=dis[i];
                now=i;
            }
        }
        ans+=minn;
        for(int j=head[now];j!=-1;j=edge[j].next){
            int to=edge[j].to;
            if(dis[to]>edge[j].w && !vis[to])
                dis[to]=edge[j].w;
        }
    }
    return ans;
}
int main(){
    for(int i=1;i<=M;i++){set[i]=i; }
    memset(head,-1,sizeof(head));
    init(); 
    //print();
    printf("%d",prim());
    return 0;
}

by huangyige123 @ 2024-04-01 21:43:57

可以在prim之后判断所有点的dis是不是inf @George_qwe

by huangyige123 @ 2024-04-01 21:45:18

如果有一个点的dis是，就输出“orz”

by George_qwe @ 2024-04-02 19:01:01

谢谢各位，已A

此贴结。

附dfs代码,供后人理解

void dfs(int x){
    if(cot[x]==0){
        cot[x]=1;
        for(int j=head[x];j!=-1;j=edge[j].next){
            dfs(edge[j].to);
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    init(); 
    //print();
    dfs(1);
    for(int i=1;i<=n;i++){
        //cout<<cot[i];
        if(cot[i]==0){
            printf("orz");
            return 0;
        }
    }
    printf("%d",prim());
    return 0;
}

勿直接抄代码