连通图__牛客网

牛客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)

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)

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)

牛客485262153号

用并查集来判断是否为连通图，注意有效边

#include <cstdio>
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int father[10001];
void InitSet(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}
int FindFather(int u) {
    if (u == father[u]) {
        return u;
    } else {
        father[u] = FindFather(father[u]);
        return father[u];
    }
}
void UnionSet(int r, int t) {
    r = FindFather(r);
    t = FindFather(t);
    father[r] = t;
}
struct edge {
    int u;//边的两个结点、权值
    int v;
    int w;
    edge(int _u, int _v, int _w) {
        u = _u;
        v = _v;
        w = _w;
    }
};
bool cmp(edge a, edge b) {
    return a.w < b.w; //从小到大最小生成树
}
int main() {
    int n,m;
    while (scanf("%d %d",&n,&m)!=EOF) {
        if(n==0&&m==0){
            break;
        }
        if(m<n-1){
            printf("NO\n");break;
        }
        int edge=0;//有效边的个数
        InitSet(n+1);
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            if(FindFather(u)!=FindFather(v)){
                edge++;
                UnionSet(u,v);
            }
        }
        if(edge==n-1){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-03-22 11:46:18 回复(0)

C

chong_0428

#include<stdio.h>

struct Point{
    int x;
    int y;
};
struct Edge{
    int from;
    int to;
    int height;
};

struct Point point[1000];
struct Edge edge[1000*999/2];
int father[1001];
int height[1001];

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

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

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

int main(){
    int n, m;
    int a, b;
    int x, y, c = 0;

    while(scanf("%d %d", &n,&m) != EOF){
        c = 0;
        if (n == 0 || m == 0) break;
        inital(n);
        for(int i = 0; i < m; i++){
            scanf("%d %d", &a, &b);
            Union(a, b);
        }
        x = Find(1);
        for(int i = 2; i <= n;i++){
            y = Find(i);
            if (x == y) continue;
            else{
                c++;
                x = y;
            }
            
        }
        if(c != 0) printf("%s\n","NO");
        else printf("%s\n", "YES");
        //printf("%d\n", c);
    }
   return 0;
}

发表于 2025-03-18 12:18:05 回复(0)

C++

水彩笔watercol

使用散列表查找法判断是否只含有一个连通分量

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

int main() {
    int n, m;
    while(cin >> n >> m){
        if(n == 0) break;
        unordered_map<int,int> graph;
        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            if(graph[a] != 0 || graph[b] != 0 || i == 0){
                graph[a]++;
                graph[b]++;
            }
        }
        int flag = 1;
        for(int i = 1; i <= n; i++){
            if(graph[i] == 0) flag = 0;
        }
        if(flag == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

发表于 2025-02-23 15:12:02 回复(0)

狗and猫

#include <stdio.h>

#include <vector>

using namespace std;

int SetCount;

void initial(vector<int> &Set)

{

for (int i = 0; i < Set.size(); i++)

{

Set[i] = i; // 表示是根节点，指向自己

}

int FindFather(int son, vector<int> &Set)

{

if (Set[son] == son)

{

return son;

}

else

{

int father = FindFather(Set[son], Set);

Set[son] = father;

return father;

}

void Union(int u, int v, vector<int> &Set)

{

int father_u = FindFather(u, Set);

int father_v = FindFather(v, Set);

if (father_u != father_v)

{

SetCount--;

}

Set[father_u] = father_v;

}

int main()

{

int n, m;

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

{

if (n == 0 && m == 0)

{

break;

}

vector<int> Set(n + 1); // 并查集

initial(Set);

SetCount = n;

int start, end;

for (int i = 0; i < m; i++)

{

scanf("%d %d", &start, &end);

Union(start, end, Set);

}

if (SetCount == 1)

{

printf("YES\n");

}

else

{

printf("NO\n");

}

return 0;

}

发表于 2025-02-08 23:31:21 回复(0)

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)

连通图

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题