连通图

[编程题]连通图

热度指数：12182 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

输出

NO
YES

算法知识视频讲解

稀有的猪

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define maxn 1010

int G[maxn][maxn];
bool vis[maxn] = {false};
int n, m;

void init()
{
    for (int i = 1; i <= n; i++)
    {
        vis[i] = false;
        for (int j = 0; j <= n; j++)
        {
            G[i][j] = 0;
        }
    }
}
void dfs(int u)
{
    vis[u] = true;
    for (int v = 1; v <= n; v++)
    {
        if (!vis[v] && G[u][v])
            dfs(v);
    }
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF && n != 0)
    {
        int a, b;
        init();
        for (int i = 0; i < m; i++)
        {   
            scanf("%d %d", &a, &b);
            G[a][b] = 1;
            G[b][a] = 1;
        }
        int cnt = 0;
        for (int u = 1; u <= n; u++) 
        {
            if (!vis[u])
            {
                dfs(u);
                cnt++;
            }
        }
        printf("%s", cnt == 1 ? "YES\n" : "NO\n");
    }
    return 0;
}

发表于 2022-03-13 12:04:03 回复(0)

Gargantua

//ky175连通图
#include<stdio.h>
#define MAXN 1001

void Init(int s[]){
	for(int i=1;i<MAXN;i++)
		s[i]=-1;
}

int Find(int s[],int x){
	while(s[x]>=0)
		x=s[x];
	return x;
}

void Union(int s[],int r1,int r2){
	if(r1==r2)return;
	else{
		if(s[r1]<s[r2]){
			s[r1]+=s[r2];
			s[r2]=r1;
		}
		else{
			s[r2]+=s[r1];
			s[r1]=r2;
		}
	}
}

int main(){
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF){
		if(n==0 && m==0)
			break;
		else{
			int count=0;
			int P[MAXN];
			Init(P);
			for(int i=0;i<m;i++){
				int a,b;
				scanf("%d %d",&a,&b);
				int root1=Find(P,a);
				int root2=Find(P,b);
				if(root1!=root2)
					Union(P,root1,root2);
			}
			for(int j=1;j<=n;j++)
				if(P[j]<0)
					count++;
			if(count==1)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
}

发表于 2022-02-13 18:40:29 回复(0)