连通图__牛客网

ccysz

//使用并查集就可以解决

#include <string.h>

#include <stdio.h>

int findroot( int number, int JH[])

{

if (JH[number]==-1) return number;

else

{

int temp= findroot (JH[number], JH);

JH[number]=temp;

return temp;

}

int main( int argc, const char * argv[]) {

int n,m;

while ( scanf ( "%d %d" ,&n,&m)!= EOF ) {

if (n==0)

break ;

int JH[1001];

int i;

for (i=1; i<=n; i++) {

JH[i]=-1;

}

for (i=1;i<=m;i++)

{

int temp,temp2;

scanf ( "%d" ,&temp);

scanf ( "%d" ,&temp2);

int root1= findroot (temp,JH);

int root2= findroot (temp2,JH);

if (root1!=root2)

{

JH[root2]=root1;

}

int count=0;

for (i=1; i<=n; i++) {

if (JH[i]==-1)

count++;

}

if (count>1)

printf ( "NO\n" );

else

printf ( "YES\n" );

}

return 0;

}

发表于 2017-01-04 15:16:11 回复(1)

TheBug

/*使用广度优先遍历判断是否为连通图*/
#include<cstdio>
#include<iostream>
#include<queue>
#define MAXN 1001
using namespace std;

queue<int> Q;
bool G[MAXN][MAXN], visit[MAXN];

void Initial(int n){                /*初始化*/
    for(int i=1;i<n+1;i++){
        visit[i]=false;
        for(int j=1;j<n+1;j++)
            G[i][j] = false;
    }
    return ;
}

void BFS(int n){
    Q.push(1);
    while(!Q.empty()){
        int i=Q.front();
        Q.pop();
        visit[i]=true;
        for(int j=1;j<n+1;j++){
            if(G[i][j] && !visit[j]) Q.push(j);
        }
    }
    return ;
}

int main(){
    int n,m,x,y;
    while(cin>>n>>m){
        if(!n && !m)
            break;
        Initial(n);
        while(m--){
            cin>>x>>y;
            G[x][y]=true;
            G[y][x]=true;
        }
        BFS(n);
        bool connected=true;
        for(int i=1;i<n+1;i++){
            if(!visit[i]){
                connected=false;
                break;
            }
        }
        if(connected) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

编辑于 2020-03-23 20:56:23 回复(1)

C/C++

奔跑的牛阿牛

运用并查集的思想，Find+Uinon，对于一个无向的连通图而言，其连通分量就是本身，再学习学习高赞同学 263保洁小妹 运用遍历的方法😁

//和浙江大学的畅通问题类似,又默写了一边，嘻嘻
#include<iostream>

using namespace std;

int father[1000];
int height[1000];

void Initial(int n){
    for(int i=1; i<=n; i++){
        father[i] = i;
        height[i] = 0;
    }
    return;
}

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[y] = x;
        }
        else if(height[x]<height[y]){
            father[x] = y;
        }
        else{
            father[x] = y;
            height[y]++;
        }
    }
    return;
}

int main(){
    int n,m;
    while(cin>>n){
        Initial(n);
        cin>>m;
        if(n==0&&m==0){
            break;
        }
        for(int i=0; i<m; i++){
            int a,b;
            cin>>a>>b;
            Union(a,b);
        }
        int answer = -1;
        for(int i=1; i<=n; i++){
            if(i==Find(i)){
                answer++;
            }
        }
        if(answer==0){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

发表于 2020-02-22 16:15:21 回复(0)

没有借口

使用并查集即可

//将每个元素看为一个集合，然后通过并查集合并集合，然后再将余下的集合连接起来即可
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m&&n!=0&&m!=0){
        int t=n-1;        //3个城市只要2个道路即连通
        int v[1000];        //保存连通的一个有效点
        memset(v,-1,sizeof(v));
        while(m--){
            int x,y;
            cin>>x>>y;
            int a=x,b=y;
            while(v[a]!=-1)a=v[a];//找代表元素
            while(v[b]!=-1)b=v[b];
            if(a==b)continue;    //该路无效，已存在有效路径
            else v[b]=x,t-=1;//合并集合，需要路径-1
        }
        if(t==0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        memset(v,-1,sizeof(v));
        
    }
    return 0;
}

发表于 2021-03-10 20:27:08 回复(0)

sSTtaArR

/*
*用并查集表征连通分量。两者在直观上是不同的，但是性质是相同的。
*/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3;
int father[maxn+5];
int n, m;

void Initial()
{
    for(int i = 1;i <= n; i++) father[i] = i;
}

int getFather(int x)
{
    int a = x;
    while(x != father[x]) x = father[x];
    //路径压缩
    while(a != father[a])
    {
        int z = a; a = father[a]; father[z] = x;
    }
    return x;
}

void Union(int a, int b)
{
    int fa = getFather(a);
    int fb = getFather(b);
    if(fa != fb) father[fa] = fb;
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n >> m && n && m)
    {
        Initial(); int u, v; 
        for(int i = 0;i < m; i++)
        {
            cin >> u >> v; Union(u, v);
        }
        int ans = 0;
        for(int i = 1;i <= n; i++) ans += father[i] == i ? 1 : 0;
        if(ans == 1) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return 0;
}

发表于 2021-01-22 21:30:25 回复(0)

Java

LHC0512

Java 解法，使用并查集

package nowcoder02.demo49;

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static class UnionFind {
        private int[] id;

        public UnionFind(int N) {
            id = new int[N];
            for(int i = 0; i < N; i++) id[i] = i;
        }

        public int find(int p) {
            return id[p];
        }

        public void union(int p, int q){
            int pRoot = find(p);
            int qRoot = find(q);
            if(pRoot == qRoot) return;
            for(int i = 0; i < id.length; i++)
                if(id[i] == pRoot)  id[i] = qRoot;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int vertex = scanner.nextInt();
            int edge = scanner.nextInt();
            UnionFind union = new UnionFind(vertex + 1);
            for (int i = 0; i < edge; i++) 
                union.union(scanner.nextInt(),scanner.nextInt());
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < vertex; i++) 
                set.add(union.find(i+1));
            System.out.println(set.size()==1?"YES":"NO");
        }
    }
}

发表于 2020-03-14 11:12:23 回复(0)

C/C++

鹰击ck

#include<stdio.h>
#define N 1001
int point[N];
int find(int x){
    return x==point[x]? x:point[x]=find(point[x]);
}
int main(){
    int m,n,x,y,u,v,count;
    for(int i=1;i<N;i++)    point[i]=i;
    while(scanf("%d%d",&n,&m)!=EOF){
        count=0;
        for(int i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            u=find(x);v=find(y);
            if(u!=v)    point[y]=u;
        }
        for(int i=1;i<=n;i++){
            if(point[i]==i)   count++;
        }
        if(count==1)    printf("YES\n");
        else    printf("NO\n");
    }
    return 0;
}

发表于 2018-03-14 20:53:50 回复(0)

Benson666

并查集
import java.util.Scanner;
public class Main {
     static int[] root;
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int m = in.nextInt();
            root = new int[n+1];
            for(int i=0;i<=n;i++)
                root[i] = -1;
            for(int i=0;i<m;i++){
                int x = in.nextInt();
                int y = in.nextInt();
                int a = findRoot(x);
                int b = findRoot(y);
                if(a!=b) root[a] = b;
            }
            int cnt=0;
            for(int i=1;i<=n;i++)
                if(root[i]==-1) cnt++;
            if(cnt==1) System.out.println("YES");
            else System.out.println("NO");
        }
    }
    
    public static int findRoot(int x){
        if(root[x]==-1) return x;
        int tmp = findRoot(root[x]);
        root[x] = tmp;
        return tmp;
    }
 
}

发表于 2018-03-07 11:41:04 回复(0)

牛客5380090号

并查集 import java.util.Scanner;

public class 连通分量 {
	private static int[] father;
	private static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			n = sc.nextInt();
			if(n==0)
				break;
			int m = sc.nextInt();
			father = new int[n+1];
			for (int i = 1; i <= n; i++) {
				father[i] = i;
			}
			for(int i = 0;i<m ;i++){
				int a = sc.nextInt();
				int b = sc.nextInt();
				union(a,b);
			}
			
			if(n<2)
				System.out.println("YES");
			else
				System.out.println("NO");
			
		}
	}

	private static void union(int a, int b) {
		int a_root = findfather(a);
		int b_root = findfather(b);
		
		if(a_root!=b_root){
			father[a_root] = b_root;
			n--;
		}

		
		
	}

	private static int findfather(int a) {
		while(father[a] != a)
			a = father[a];
		return a;
	}

}

发表于 2017-08-20 21:40:16 回复(0)

263保洁小妹

用邻接矩阵存储无向图，然后遍历图，即可确定是不是连通图

#include <stdio.h>
#define N 1001

void Visit(bool G[N][N], bool visit[N], int n, int x)
{
    visit[x]=true;//先访问1
    for(int i=1; i<=n; i++)
    {
        if(G[i][x]==true&&visit[i]==false) Visit(G, visit, n, i);
    }
}

int main()
{
    bool G[N][N];//用邻接矩阵存储这个图
    bool visit[N];
    int n, m, x, y;
    while(scanf("%d %d", &n, &m)!=EOF)
    {
        for(int i=1; i<=n; i++)//初始化
        {
            visit[i]=false;
            for(int j=1; j<=n; j++)
            {
                G[i][j]=false;
            }
        }
        while(m--)
        {
            scanf("%d %d", &x, &y);
            G[x][y]=true;
            G[y][x]=true;
        }
        Visit(G, visit, n, 1);
        bool connected=true;
        for(int i=1; i<=n; i++)
        {
            if(!visit[i]) connected=false;
        }
        if(connected) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

发表于 2018-02-25 08:55:22 回复(2)

C/C++

|讨厌鬼|

#include<stdio.h>
#define N 1001
int FindRoot(int Tree[],int x){
    if(Tree[x]==-1) return x;
    else{
        Tree[x]=FindRoot(Tree,Tree[x]);
        return Tree[x];
    }
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        int Tree[N];
        int i,a,b;
        for(i=1;i<=n;i++)
            Tree[i]=-1;
        while(m--){
            scanf("%d%d",&a,&b);
            a=FindRoot(Tree,a);
            b=FindRoot(Tree,b);
            if(a!=b) Tree[b]=a;
        }
        int ans=0;
        for(i=1;i<=n;i++)
            if(Tree[i]==-1) ans++;
        puts(ans>1?"NO":"YES");
    }
}

发表于 2018-01-19 18:47:34 回复(0)

C++

帅奶哟。

#include <cstdio>
#include <iostream>

using namespace std;

const int MAXN = 1000+10;

int father[MAXN];
int height[MAXN];

void Init(int n);
int Find(int x); 
void Union(int x, int y);

// 连通图 ——运用并查集判断是否为连通图 
int main() {
	int n, m;
	while (scanf("%d %d", &n, &m) != EOF) {
		if (n == 0 && m == 0) {
			break;
		}
		// 初始化father
		Init(n);
		for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			Union(x, y);
		}
		
		int answer = 0;// 若连通，所有节点的Find值都 == t 
		for (int i = 1; i <= n; i++) {
			if (Find(i) == i) {// 存在不止一颗树 
				answer++;
			}
		} 
		if (answer == 1) {
			cout << "YES" << endl;
		}else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

// 初始化并查集
void Init(int n) {
	for (int i = 1; i <= n; i++) {// 注意小于等于n！并且从1开始 
		father[i] = i;
		height[i] = 0; 
	}
	return;
} 

// 寻找父节点
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;
}

发表于 2023-03-27 15:15:51 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

const int Max=1000;
int father[Max];
int height[Max];

void Initial(int n){
    for(int i=1;i<=n;i++){
        father[i]=i;
        height[i]=0;
    }
    return ;
}

int Find(int x){
    if(x!=father[x]){
        father[x]=Find(father[x]);
    }
    return father[x];
}

void Union(int a,int b){
    int x=Find(a);
    int y=Find(b);
    if(x!=y){
        if(height[x]>height[y]){
            father[y]=x;
        }
        else if(height[x]<height[y]){
            father[x]=y;
        }
        else{
            father[y]=x;
            height[x]++;
        }
    }
    return ;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        Initial(n);
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            Union(a,b);
        }
        int component=0;
        for(int i=1;i<=n;i++){
            if(i==Find(i)){
                component++;
            }
        }
        if(component==1){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

发表于 2022-10-13 15:00:27 回复(1)

zbt_123456

别再并查集了，赶紧图论吧，并查集函数多的你眼不花吗

#include <iostream>
#include<vector>
using namespace std;
void dfs(vector< vector<int> >&graph,int i,vector<bool>& v){
    v[i] = true;
    for(int j=0;j<graph[i].size();j++){
        if(graph[i][j]==1&&!v[j]) dfs(graph,j,v);
    }
}
int main() {
    int n,m;
    while(cin>>n>>m&&m*n!=0){
        vector< vector<int> > g(n,vector<int>(n,0));
        vector<bool> visit(n,false);
        for(int i=0;i<n;i++)
            g[i][i] = 1;
        while(m--){
            int a,b;
            cin>>a>>b;
            g[a-1][b-1] = 1;
            g[b-1][a-1] = 1;
        }
        int result = 0;
        for(int i =0;i<n;i++){
            if(!visit[i]){
                dfs(g,i,visit);
                result++;
            }
        }
        result==1?cout<<"YES"<<endl:cout<<"NO"<<endl;
    }
    return 0;
}

发表于 2024-03-30 18:18:35 回复(0)

C++

Forgery

#include<stdio.h>


int father[2000];

void init(int n){
    for(int i=0;i<=n;i++){
        father[i] = i;
    }
}
int FindFather(int n){
    if(father[n]==n) return n;
    else{
        father[n] = FindFather(father[n]);
        return father[n];
    }
}
void unoin(int a,int b){
     int r1 = FindFather(a);
     int r2 = FindFather(b);
     father[r2] = r1;
}
int main(){
    int n,m;

       
       while(scanf("%d%d",&n,&m)!=EOF){

       int edge = 0;
        init(n);
        if(n==0&&m==0) break;
        else{
            for(int i=0;i<m;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                int r1 = FindFather(a);
                int r2 = FindFather(b);
                if(r1!=r2){
                     father[r1] = r2;
                     edge++;
                }
                  
            }
        }
         
        if(edge+1==n)
        printf("YES\n");
        else printf("NO\n");
    }
}

编辑于 2024-03-15 16:28:31 回复(0)

C++

无问西东gmy

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000;

vector<int>father(MAXN);                        //父亲结点
vector<int>height(MAXN);                        //结点高度

void Initial(int n) {                           //初始化
    for (int i = 0; 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[y] < height[x]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        Initial(n);                             //初始化
        while (m--) {
            int x, y;
            cin >> x >> y;
            Union(x, y);                        //合并集合
        }
        int component = 0;                      //连通分量
        for (int i = 1; i <= n; i++) {
            if (Find(i) == i) {                 //集合数目
                component++;
            }
        }
        cout << (component == 1 ? "YES" : "NO") << endl;
    }
    return 0;
}

编辑于 2024-02-20 23:26:39 回复(0)

考研上岸tongji

#include "bits/stdc++.h"

using namespace std;
int n, m;
const int maxn = 1001;
int father[maxn];
int height[maxn] = {0}; //这里把height初始化为0即可，后面并操作时再修改
void initial() {
    for (int i = 0; i <= n; i++) {
        father[i] = i;   // 先默认设置为自身即可
    }
    return;
}

int find(int x) {
    while (x != father[x]) {
        x = father[x];
    }
    return x;
}

void Union(int x, int y) {    //union 是默认关键字，应该避免使用
    int f_a = find(x);
    int f_b = find(y);
    if (f_a != f_b) {
        if (height[f_a] > height[f_b]) {
            father[f_b] = f_a;
        } else if (height[f_a] < height[f_b]) {
            father[f_a] = f_b;
        } else {
            father[f_a] = f_b;
            height[f_b]++;
        }
    }

}

int main() {
    while (scanf("%d %d" , &n,&m)!=EOF) {
        if(n==0 && m==0)    break;

        initial();
        for (int i = 0; i < m; i++) {
            int temp1, temp2;
            scanf("%d %d", &temp1, &temp2);
            Union(temp1, temp2);
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (i == father[i]) { res++; }
        }
        if (res == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

编辑于 2024-01-06 14:57:45 回复(0)

霸天龙王

#include<cstdio>
#define N 1000

using namespace std;

int father[N];
int height[N];
void Init(int n){
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        height[i] = 1;
    }
}

int Find(int x){
    if(x!=father[x]){
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y,int &num){
    x = Find(x);
    y = Find(y);
    if (x != y) {
        --num;
    }
    if (height[x] < height[y]) {
        father[x] = y;
    }else if(height[x] > height[y]){
        father[y] = x;
    } else{
        father[y] = x;
        ++height[x];
    }
}

int main(){
    int m, n;
    while(scanf("%d%d",&n,&m)!=EOF) {
        if (m == 0 && n == 0) {
            break;
        }
        Init(n);
        int num = n;
        for (int i = 0; i < m; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            Union(x, y,num);
        }
        if (num == 1) {
            printf("YES\n");
        } else{
            printf("NO\n");
        }
    }
}

发表于 2023-03-08 18:04:36 回复(0)

C++

上岸上岸冲冲冲

#include<stdio.h>
int father[2000];
void Init(int n){
    //初始化，令所有节点的祖先是自己
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
}
int Find(int x){
    //查找节点x的祖先
    if(x==father[x]){
        //x就是树根
        return father[x];
    }
    else{
        return Find(father[x]);//递归寻找x的祖先
    }
}
void Union(int x,int y,int &num){
    //合并并查集
    x=Find(x);
    y=Find(y);
    if(x==y){
        //x与y在一个集合当中
        return;
    }
    else{
        //x与y不在一个集合，合并两个集合
        //令y的祖先是x
        father[y]=x;
        num--;
    }
}
int main(){
    int n,m;//n个节点，m条边
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0){
            break;
        }
        Init(n);
        int num=n;//初始状态n个并查集
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            Union(x,y,num);
        }
        if(1==num){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
}

发表于 2023-03-06 21:53:23 回复(0)

会时Kk

数组实现的并查集应该算很初级的算法
#include <iostream>
#include <vector>
using namespace std;

vector<int> parent;

int find(int a){
    if(parent[a]==-2){
        parent[a] = -1;
        return a;
    }
    if(parent[a] == -1) return a;
    if(parent[a]!=-1) return find(parent[a]);
    return a;
}

void to_union(int a,int b){
    int x = find(a-1);
    int y = find(b-1);
    if(y!=x){
        parent[b-1] = x;
    }
}
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        parent.resize(a,-2);
        for(int i =0; i < b;++i){
            int x,y;
            cin >> x >>y;
            to_union(x,y);
        }
        int count = 0;
        for(int i=0; i < a;++i){
            if(parent[i]==-1||parent[i]==-2) count++;
        }

        if(count ==1) cout <<"YES" << endl;
        else cout <<"NO" << endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2023-03-06 15:19:23 回复(0)

连通图

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题