连通图【并查集】

来杯Sherry

发布于 2023-05-25 15:04:34

2950

发布于 2023-05-25 15:04:34

文章被收录于专栏：第一专栏第一专栏

描述

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。

输入描述：

每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

输出描述：

对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

示例1

输入： 4 3 1 2 2 3 3 2 3 2 1 2 2 3 0 0 输出： NO YES
并查集 Initial() //初始化 Union() //合并，路径压缩 Find() //查询，找爹用途:判断连通图、求连通分量

#include<iostream>
using namespace std;
int n,m;
int father[1010];
int height[1010];
void Initial(){
    for(int i=1;i<=n;i++){
        father[i]=i;//自己是自己的父亲
        height[i]=0;//高度为0
    }
}
int Find(int x){//找爹
    if(x !=father[x]){//找到根节点 才返回
        father[x] = Find(father[x]);
    }
    return father[x];
}
void Union(int x,int y){
    x =Find(x);
    y =Find(y);
    if(x!=y){
            if(height[x] < height[y]){ //矮子合并到高个子树上，整体高度不变
            father[x] =y;

        }else if(height[x]>height[y]){
            father[y]=x;
        }else {
            father[y] =x;
            height[x]++;
        }
    }
    return;
}
int main(){

    while(cin>>n>>m){
        if(n == m && n == 0)break;
        Initial();
        while(m--){
            int x,y;
                cin>>x>>y;
            Union(x,y);
            
        }
        int compenent =0;
        for(int i=1;i<=n;i++){
            if(Find(i) == i)compenent++;//连通分量个数，数数根节点
        }
        if(compenent == 1){
            cout<<"YES"<<endl;
        }else {
            cout<<"NO"<<endl;
        }
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-03-17，如有侵权请联系 cloudcommunity@tencent.com 删除

find