[编程题]连通图
- 热度指数：12166 时间限制：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
并查集 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)
更多回答
//使用并查集就可以解决
#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)
/*使用广度优先遍历判断是否为连通图*/
#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)
运用并查集的思想，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)
/*
*用并查集表征连通分量。两者在直观上是不同的，但是性质是相同的。
*/
#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 解法，使用并查集
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)
#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)
并查集
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)
用邻接矩阵存储无向图，然后遍历图，即可确定是不是连通图
#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)
#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)
#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)
#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;
}
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)
别再并查集了，赶紧图论吧，并查集函数多的你眼不花吗
#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)
#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)
#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)
#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)
#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)
数组实现的并查集应该算很初级的算法
#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)
问题信息
难度：
79条回答
108收藏
8346浏览
通过挑战的用户
查看代码-
2023-03-14 11:06:38 -
2023-03-13 15:28:35
-
2023-03-13 15:04:20 -
2023-03-13 11:20:28
-
2023-03-13 09:57:56
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
