include stdio include math include iostream include vector using names

 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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector < vector<int> > g;
vector<char> color;
vector<int> p;
int cycle_st, cycle_end;
bool dfs(int v) {
color[v] = 1;
for (size_t i = 0; i<g[v].size(); ++i) {
int to = g[v][i];
if (color[to] == 0) {
p[to] = v;
if (dfs(to)) return true;
}
else if (color[to] == 1) {
cycle_end = v;
cycle_st = to;
return true;
}
}
color[v] = 2;
return false;
}
int main() {
cin >> n >> m;
g = vector<vector<int>>(n);
for (int i = 0; i<m; i++)
{
int a, b;
cin >> a >> b;
g[a - 1].push_back(b - 1);
}
p.assign(n, -1);
color.assign(n, 0);
cycle_st = -1;
for (int i = 0; i < n; ++i)
if (dfs(i))
break;
if (cycle_st == -1)
puts("Acyclic");
else {
puts("Cyclic");
vector<int> cycle;
cycle.push_back(cycle_st);
for (int v = cycle_end; v != cycle_st; v = p[v])
cycle.push_back(v);
cycle.push_back(cycle_st);
reverse(cycle.begin(), cycle.end());
for (size_t i = 0; i < cycle.size(); ++i)
printf("%d ", cycle[i] + 1);
}
system("pause");
}