C ++深度优先搜索（DFS）实现

本文介绍了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

即时演示连结