1282: 连通图

题目描述

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

输入

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

输出

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

样例输入

4 3
4 3
1 2
1 3
5 7
3 5
2 3
1 3
3 2
2 5
3 4
4 1
7 3
6 2
3 1
5 6
0 0

样例输出

YES
YES
NO

AC代码（并查集）

此代码需要理解并查集的内核：传送门

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn = 1000 + 10;
const int maxm = maxn * (maxn - 1) / 2 + 100;

int parent[maxn], depth[maxn];

void init(int n) {
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
		depth[i] = 1;
	}
}

int find(int i) {
	return i == parent[i] ? i : (parent[i] = find(parent[i]));
}

void unionNode(int p, int q) {
	p = find(p);
	q = find(q);
	if (p == q)return;
	else if (depth[p] > depth[q]) {
		parent[q] = p;
	}
	else if (depth[p] < depth[q]) {
		parent[p] = q;
	}
	else {
		parent[q] = p;
		depth[p]++;
	}
}

bool isConnected(int n) {
	int ans = 0;
	for (int i = 1; i <= n; i++) {//遍历所有顶点
		if (parent[i] == i) {//统计根节点的个数
			ans++;
		}
	}
	if (ans == 1)return true;//只有一个根节点，说明只有一个连通图
	else return false;
}


int main()
{
	int n, m;
	while (cin >> n >> m && n) {
		init(n);
		int x, y;
		for (int i = 1; i <= m; i++) {
			cin >> x >> y;
			unionNode(x, y);
		}
		if (isConnected(n))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}
	

BFS和DFS

BFS和DFS详解

邻接表存图（map二维数组）,BFS遍历图：传送门
邻接表存图的技巧可以参考此份资料：传送门

#include<stdio.h>
#include<cmath>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1000 + 10;
vector<int> map[maxn];   //map[i]保存i节点的邻居节点   
int vis[maxn];    
void dfs(int r,int &ans){
    vis[r]=1;
    //cout<<r<<" ";   //将这个注释打开可以看看遍历结果，加深一下bfs的了解
    ans++;
    for(int i=0;i<map[r].size();i++){
        if(vis[map[r][i]]==0){//当结点map[r][i]没有被遍历过时，进入if{}
            dfs(map[r][i],ans);
        }
    }
} 
int main(){
    int n,m,ans;
    while(cin>>n>>m){
        if(n==0 && m==0) break;
        ans=0;
        memset(vis,0,sizeof(vis));
        memset(map,0,sizeof(map));
        int a,b;
        for(int i=0;i<m;i++){  //构建地图  (邻接表儿)
            cin>>a>>b;
            map[a].push_back(b);
            map[b].push_back(a);
        }
        dfs(a,ans);
        if(ans==n){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}