blob: bb0bd22ee611676dac148320cf4cb23609c40820 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <iostream>
#include <list>
#define WHITE 0
#define GREY 1
#define BLACK 2
#define INF 99999
using namespace std;
int checked[INF] = {WHITE};
int d[INF] = {0};
int f[INF] = {0};
int t = 1;
void dfs(list<int> lista[], int start) {
checked[start] = GREY;
d[start] = t++;
for(auto it = lista[start].begin(); it != lista[start].end(); it++) {
if(checked[*it] == WHITE)
dfs(lista, *it);
}
checked[start] = BLACK;
f[start] = t++;
cout << start << '(' << d[start] << ',';
cout << f[start] << ')' << endl;
}
int main() {
int u, w;
int e;
cin >> e;
list<int> lista[INF];
for(int i = 0; i < e; ++i) {
cin >> u >> w;
lista[u].push_back(w);
}
dfs(lista, 0); //0 is the start
/* example:
http://pages.cs.wisc.edu/~mcw/cs367/lectures/images/dfs.gif
#input
8
0 1
0 5
1 2
2 0
1 3
3 4
4 2
1 4
#output
2(3,4)
4(6,7)
3(5,8)
1(2,9)
5(10,11)
0(1,12)
*/
return 0;
}
|
