首页 > 试题广场 >

连通图

[编程题]连通图
  • 热度指数：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

输入

4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0

输出

NO
YES
算法知识视频讲解
开通博客
头像 Double厚
发表于 2020-11-17 17:04:26
使用并查集判断连通图 import java.util.Scanner; public class Main { static int[] f = new int[1005]; public static void init() { for (int i = 0; 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 慢慢且漫漫~
发表于 2022-05-05 10:40:31
一、解题思路 （1）判断所有顶点连通？ （2）什么是所有顶点连通？ 答：所有顶点都有路径相连 （3）怎么保证有路径相连？ 答：看是否属于同一个集合 （4）如何判断是一个集合？ 答：集合逻辑上表示为树结构，对于每一个元素不断向上找根节点，如果根节点相同则连个元素是一个集合 综上所述：判断所有顶点连通 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 不红红黑路同
发表于 2022-03-05 09:56:24
#include <iostream> using namespace std; int father[100010]; int height[100010]; void initial(int n){ for(int i=0;i<=n;i++){ fa 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 wbc990512
发表于 2021-01-24 13:18:38
妈妈我终于学会并查集啦！ #include<stdio.h> int father[1005] = {0}; void init(int father[]) { for(int i = 0;i<1005;i++) father[i] = i; ret 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 爱喝零度可乐
发表于 2023-03-14 14:21:09
#define N 2000 #include<cstdio> int father[N]; int height[N]; void Init(int n) { for (int i = 1; i <= n ; ++i) { father[i] = i ; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 yyer
发表于 2023-03-07 21:37:36
#include <iostream> #include <queue> #include <vector> using namespace std; const int N=1005; bool visited[N]={false}; int n,m,a,b,c 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 爱读书的伊泽瑞尔很有胆量
发表于 2023-03-13 15:30:16
#include<cstdio> using namespace std; #define N 1000 int father[N];//存储了父亲的下标 int high[N];//存储了某个根的树的高度 void Init(int n){ //最开始每个元素单独构建一个集合, 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客774160366号
发表于 2023-07-05 13:01:51
#include <stdio.h> //思想：并查集 //拥有同一祖先father的顶点一定是联通的，起初将每个顶点的祖先都设为自己，之后每读入一条边x1，x2都将x2的最终祖先的祖先设为x1的祖先 //从逻辑上讲，也就是将以x2祖先为根节点的连接树，接到以x1祖先为根节点的树上，这样 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在考古的小鱼干很有气魄
发表于 2023-03-12 09:19:36
#include <bits/stdc++.h> #define MAX 1000 using namespace std; typedef struct{ int a,b; }Road; Road roads[MAX]; int vexset[MAX]; int getroot(i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Huster水仙
发表于 2023-02-02 11:58:43
#include<iostream> using namespace std; const int maxn=1010; int Father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<=n;i 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

图 并查集
难度：
79条回答 8380浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号