blob: 8174030c3b34ed6fedd54c13863fb0db946769ab (
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
66
67
68
69
|
#include <iostream>
#include <list>
#include <queue>
#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 bfs(const list<int> lista[], int start) {
queue<int> coda;
int checked[999] = {WHITE};
coda.push(start);
checked[start] = GREY;
while(!coda.empty()) {
int corrente = coda.front();
coda.pop();
if(checked[corrente] == GREY) {
cout << corrente << ' ';
for(auto it = lista[corrente].begin(); it != lista[corrente].end(); ++it) {
coda.push(*it);
if(checked[*it] != BLACK)
checked[*it] = GREY;
}
checked[corrente] = BLACK;
}
}
}
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);
}
bfs(lista, 0); //0 is the start
/* example:
http://pages.cs.wisc.edu/~mcw/cs367/lectures/images/bfs.gif
#input
8
0 1
0 5
1 2
2 0
1 3
3 4
4 2
1 4
#output
0 1 5 2 3 4
*/
return 0;
}
|
