连通图

[编程题]连通图

热度指数：13816 时间限制：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

算法知识视频讲解

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)

稀有的猪

#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)