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
|
#include <iostream>
#include <vector>
#include <list>
using graph = std::vector<std::list<int>>;
enum class color : char
{
white,
gray,
black
};
bool has_cycle_cc(const graph& g, int vertex, std::vector<color>& colors)
{
const auto& adjacent = g[vertex];
colors[vertex] = color::gray;
for(int child : adjacent)
{
if(colors[child] == color::gray)
return true;
if(has_cycle_cc(g, child, colors))
return true;
}
colors[vertex] = color::black;
return false;
}
bool has_cycle(const graph& g)
{
std::vector<color> colors(g.size(), color::white);
for(int vertex = 0; vertex < g.size(); vertex++)
{
if(colors[vertex] == color::white && has_cycle_cc(g, vertex, colors))
return true;
}
return false;
}
int main()
{
graph g = {
/* 0 */ {1, 2},
/* 1 */ {3, 2},
/* 2 */ {},
/* 3 */ {2, 0}
}; // cycle: 0 -> 1 -> 3 -> 0
std::cout << has_cycle(g);
}
|
