C ++深度优先搜索(DFS)实现 [英] C++ Depth First Search (DFS) Implementation
本文介绍了C ++深度优先搜索(DFS)实现的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我试图实现在Competitive Programming 1书中描述的以下DFS代码:
I am trying to implement the following DFS code described at Competitive Programming 1 book:
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 10
#define DFS_BLACK 1
#define DFS_WHITE -1
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
vi dfs_num;
vector<vii> adj(MAX);
void dfs(int u) {
dfs_num[u] = DFS_BLACK;
for (int i = 0; i < (int)adj[i].size(); i++) {
ii v = adj[u][i];
if (dfs_num[v.first] == DFS_WHITE)
dfs(v.first);
}
printf(" %d", u);
}
int main() {
int v, e, x, y;
scanf("%d %d", &v, &e);
for (int i = 0; i < e; i++) {
scanf("%d %d", &x, &y);
adj[x].push_back(ii(y, 1));
adj[y].push_back(ii(x, 1));
}
int numCC = 0;
dfs_num.assign(v, DFS_WHITE);
for (int i = 0; i < v; i++)
if (dfs_num[i] == DFS_WHITE)
printf("Component %d:", ++numCC), dfs(i), printf("\n");
printf("There are %d connected components\n", numCC);
}
我想要得到的是:
Input: Output:
9 7 Component 1: 0 1 2 3 4
0 1 Component 2: 5
1 2 Component 3: 6 7 8
1 3 There are 3 connected components
2 3
3 4
6 7
6 8
对于以下图表:
但我得到组件1:3 2 1我做错了什么?
But I am getting "Component 1: 3 2 1" then it crashes. What am I doing wrong?
任何帮助。
推荐答案
for (int i = 0; i < (int)adj[i].size(); i++) {
into:
for (int i = 0; i < (int)adj[u].size(); i++) {
// ^ u, not i
这篇关于C ++深度优先搜索(DFS)实现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文