• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

06-图1 列出连通集

浙大mooc 站点默认 1个月前 (11-10) 15次浏览 已收录 0个评论

00f99065cdc1e85d88508e1aa426d3b3.png

题目很简单,我没用教材上给的图结构,不然太麻烦了,这是个无加全的无向图。。。一个二维数组就搞定了

#include<iostream>
#include<malloc.h>
#include<queue>
#define max 50
using namespace std;
int map[max][max];
int flag[max];
int n, e;
void dfs(int v){
	flag[v] = 1;
	cout <<" "<<v;
	for (int i = 0; i < n; i++) {
		if (!flag[i] && map[v][i])
			dfs(i);
	}
}
void bfs(int v){
	queue<int> q;
	flag[v] = 1;
	cout <<" "<<v;
	q.push(v);
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		for (int i = 0; i < n; i++) {
			if (!flag[i] && map[tmp][i]) {
				flag[i] = 1;
				cout <<" "<<i;
				q.push(i);
			}
		}
	}
}
int main() {
	cin >> n >> e;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] = 0;
			map[j][i] = 0;
		}
	}
	for (int i = 0; i < e; i++) {
		int tmpi, tmpj;
		cin >> tmpi >> tmpj;
		map[tmpi][tmpj] = 1;
		map[tmpj][tmpi] = 1;
	}
	for (int i = 0; i < n; i++) {
		flag[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		if (!flag[i]) {
			cout << "{";
			dfs(i);
			cout << " }"<<endl;
		}
	}
	for (int i = 0; i < n; i++) {
		flag[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		if (!flag[i]) {
			cout << "{";
			bfs(i);
			cout << " }" << endl;;
		}
	}
}


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:06-图1 列出连通集
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到