06-图1 列出连通集

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

代码语言：javascript复制

#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 人点赞