Applications
Here are some algorithms where DFS is used:
- Finding connected components.
- Cycle detection.
- Topological sorting.
- Finding 2-(edge or vertex)-connected components.
- Finding strongly connected components.
- Solving puzzles with only one solution, such as mazes.
topcoder: DFS
Imagine we have an undirected graph. The simplest way to store a graph in STL is to use the lists of vertices adjacent to each vertex. This leads to the vector< vector<int> > W structure, where W[i] is a list of vertices adjacent to i. Let’s verify our graph is connected via DFS:
/*
Reminder from Part 1:
typedef vector<int> vi;
typedef vector<vi> vvi;*/
int N; // number of vertices
vvi W; // graph
vi V; // V is a visited flag
void dfs(int i) {
if(!V[i]) {
V[i] = true;
for_each(all(W[i]), dfs);
}
}
bool check_graph_connected_dfs() {
int start_vertex = 0;
V = vi(N, false);
dfs(start_vertex);
return (find(all(V), 0) == V.end());
}
Problem: topcoder: CactusCount
用一个cycles[]存每个vertex所在的cycle的数目。用DFS进行cycle detection,每碰到一个cycle,将cycle 内所有元素 cycle[i]++。每一次DFS完毕，这一个connected component 内部如果至少有一个vertex的cycle[i] >= 2，则此component 不是cactus.
由于找到每个cycle后要回溯找cycle内所有元素，我们需要保存visit的路径。两种方法
- 每个元素保存一个parent, p[]可以查到每个元素的parent
- 用一个deque保存整条路径 （编程略简单）
下面分别给出了两种实现：
typedef vector<int> vi;
vector<vi> adj; // adj list
int vv [201]; // visited vertex in DFS;
int p[201]; // parent of node i
int cycle[201]; // # of times in a cycle
int maxcycle;
void checkmax(int &a, int b) {
if(b > a) a = b;
}
void DFS(int i, int n, int c = 0) {
vv[i] = 0; // visiting
//printf("visiting %d\n", i+1);
// visit all neighbors of i
for(int j = 0; j < adj[i].size(); ++j) {
// get the j-th neighbor: k
int k = adj[i][j];
// new vertex, first visit
if(vv[k] == -1) {
// assign i as k's parent
p[k] = i;
// visit k
DFS(k, n, c);
}
// detect a cycle : back edge vv[k] == 0
else if(vv[k] == 0 && k != p[i]) {
// actually if maxcycle >=2
// we do not need to mark any more
// just visit all and leave this component, right?
//printf("cycle %d ", k+1);
cycle[k] ++; checkmax(maxcycle, cycle[k]);
//printf("%d ", i+1);
cycle[i] ++; checkmax(maxcycle, cycle[i]);
int parent = p[i];
do {
//printf("%d ", parent+1);
cycle[parent] ++; checkmax(maxcycle, cycle[parent]);
parent = p[parent];
} while(parent != k);
//printf("%d \n", k+1);
continue;
}
}
vv[i] = c;
//printf("end visiting %d, max cycle %d\n", i+1, cycle[i]);
}
int CactusCount::countCacti(int n, vector <string> edges) {
if(edges.empty()) return n;
string edge;
for(int i = 0; i < edges.size(); ++i)
edge += edges[i];
for(int i = 0; i < edge.size(); ++i)
if(edge[i]==',') edge[i] = ' ';
adj.clear();
adj.resize(n, vi());
memset(vv,-1, sizeof(vv));
memset(p, 0, sizeof(p));
memset(cycle, 0, sizeof(cycle));
stringstream ss(edge);
int a, b;
while(ss >> a >> b) {
--a, --b;
adj[b].push_back(a) ; adj[a].push_back(b);
}
int cnt = 0, c = 1;
for(int i = 0; i < n; ++i) if(vv[i] == -1) {
p[i] = -1;
maxcycle = 0;
DFS(i, n, c);
//printf("component %d: %d, size %d\n", c, maxcycle, component[c].size());
if(maxcycle <= 1) ++cnt;
++c;
}
return cnt;
}
// ----------------------------------------------------------
// use deque to save visiting path
vector<int> adj[200]; // adj list
int col[200]; // vertex color
int cycles[200]; // # of times in a cycle
bool iscacti; // is the current component a cacti
deque<int> path; // for backtrace
// visit vertex v whose parent is p
void dfs(int v, int p) {
// visiting v
col[v] = 1;
path.push_front(v);
for(int j = 0; j < adj[v].size(); ++j) {
int k = adj[v][j];
// unvisited
if(col[k] == 0) dfs(k, v);
// back edge detected
else if(col[k] == 1 && k != p) {
deque<int>::iterator root = ++find(ALL(path), k);
for(deque<int>::iterator it = path.begin(); it!= root; ++it)
if(++ cycles[*it] > 1) iscacti = false;
}
}
path.pop_front();
col[v] = 2;
}
int CactusCount::countCacti(int n, vector <string> edges) {
REP(i, n) {
adj[i].clear();
col[i] = cycles[i] = 0;
}
stringstream ss;
for(vector<string>::iterator it = edges.begin(); it != edges.end(); ++it)
ss << *it;
int a, b;
while(ss >> a >> b) {
ss.ignore(1); --a, --b;
adj[b].push_back(a) ; adj[a].push_back(b);
}
int cnt = 0;
memset(cycles, 0, sizeof(cycles));
memset(col, 0, sizeof(col));
REP(i,n) if(col[i] == 0) {
iscacti = true;
dfs(i, -1);
if(iscacti) ++cnt;
}
return cnt;
}
Example: 
DFS visiting log
-----------------------------------
visiting 1
visiting 2
visiting 3
visiting 4
visiting 5
cycle 3 5 4 3
end visiting 5, max cycle 1
end visiting 4, max cycle 1
cycle 1 3 2 1
end visiting 3, max cycle 2
end visiting 2, max cycle 1
end visiting 1, max cycle 1
------------------------------------
component 1: maxcycle 2
------------------------------------
visiting 6
visiting 7
visiting 8
cycle 6 8 7 6
visiting 9
visiting 10
visiting 11
cycle 9 11 10 9
end visiting 11, max cycle 1
end visiting 10, max cycle 1
end visiting 9, max cycle 1
end visiting 8, max cycle 1
end visiting 7, max cycle 1
end visiting 6, max cycle 1
------------------------------------
component 2: maxcycle 1
------------------------------------
visiting 12
visiting 13
end visiting 13, max cycle 0
end visiting 12, max cycle 0
------------------------------------
component 3: maxcycle 0
------------------------------------
visiting 14
visiting 15
visiting 16
visiting 17
cycle 14 17 16 15 14
end visiting 17, max cycle 1
cycle 14 16 15 14
end visiting 16, max cycle 2
end visiting 15, max cycle 2
end visiting 14, max cycle 2
------------------------------------
component 4: maxcycle 2
------------------------------------
Test Case #3...PASSED
