STANAANDREY

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