# find cycle in undir graph(graph paint algo)

Sep 21st, 2020
1,192
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<bits/stdc++.h>
2. using namespace std;
3. const int NMAX = 1e5 + 3;
4. int n, m;
5. vector<int> graph[NMAX];
6. enum States {
7.     UNVIS,
8.     INSIDE,
9.     EXITED
10. };
11. int daddy[NMAX];
12. States nstate[NMAX];
13. pair<int, int> cycleLim(-1, -1);
14.
15. void read() {
16.     cin >> n >> m;
17.     assert(n > 0 && n < NMAX);
18.     for (int i = 0; i < m; i++) {
19.         int a, b;
20.         cin >> a >> b;
21.         assert(a >= 0 && a < n && b >= 0 && b < n);
22.         graph[a].push_back(b);
23.         graph[b].push_back(a);
24.     }
25. }
26.
27. bool dfs(int node, int daddy) {
28.     nstate[node] = INSIDE;
29.     for (auto it : graph[node]) {
30.         if (it == daddy)
31.             continue;
32.         if (!nstate[it]) {
33.             ::daddy[it] = node;
34.             if (dfs(it, ::daddy[it]))
35.                 return true;
36.         } else if (nstate[it] == INSIDE) {
37.             cycleLim = make_pair(it, node);
38.             return true;
39.         }
40.     }
41.     nstate[node] = EXITED;
42.     return false;
43. }
44.
45. void findCycle() {
46.     fill(daddy, daddy + NMAX, -1);
47.     fill(nstate, nstate + NMAX, UNVIS);
48.     for (int i = 0; i < n; i++)
49.         if (!nstate[i] && dfs(i, daddy[i]))
50.             break;
51.     if (cycleLim.first == -1) {
52.         puts("acyclic");
53.         return;
54.     }
55.     vector<int> cycle = {cycleLim.first};
56.     for (int i = cycleLim.second; i != cycleLim.first; i = daddy[i])
57.         cycle.push_back(i);
58.     cycle.push_back(cycleLim.first);
59.     reverse(cycle.begin(), cycle.end());
60.     for (size_t i = 0; i < cycle.size(); i++) {
61.         cout << cycle[i];
62.         if (i != cycle.size() - 1)
63.             cout << "->";
64.     }//*/
65. }
66.
67. int main () {
68.     read();
69.     findCycle();
70.     return 0;
71. }
72.
RAW Paste Data