以下程序使用深度优先搜索(DFS)计算一个无向图(使用邻接矩阵 g 存储)中连通分量的个数。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
int n; // 顶点数
int g[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记数组
void dfs(int v) {
① = true;
for (int i = 0; i < n; i++) {
if (② && !visited[i]) {
③;
}
}
}
int main() {
cin >> n;
// 读入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
memset(visited, false, sizeof(visited));
int components = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
④;
⑤;
}
}
cout << components << endl;
return 0;
}
①处应填( )
visited[i]
visited[v]
v
i