Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef vector<bool> vb;
  6. typedef vector<int> vi;
  7. typedef vector<vi> vvi;
  8.  
  9. int n=0;
  10.  
  11. vi p, color; // parents, color
  12. vvi g; // all cycles, graph
  13.  
  14. set<vi> cycle, box;
  15. void add_cycle(int cycle_end, int cycle_st) {
  16.     vi curr_cycle, sorted;
  17.  
  18.     curr_cycle.push_back(cycle_st);
  19.     for (int v=cycle_end; v!=cycle_st; v=p[v])
  20.         curr_cycle.push_back(v);
  21.     sorted = curr_cycle; // создать копию без последнего элемента
  22.     curr_cycle.push_back(cycle_st);
  23.     // reverse(curr_cycle.begin(), curr_cycle.end()); // не обязательно
  24.  
  25.     sort (sorted.begin(), sorted.end());
  26.  
  27.     // неориентированный граф
  28.     // избавляюсь от вырожденности (v - to - v)
  29.     if (curr_cycle.size()>3 && count(box.begin(), box.end(), sorted)==0) {
  30.         cycle.insert(curr_cycle);
  31.         box.insert(sorted);
  32.     }
  33. }
  34.  
  35. void dfs(int v) {
  36.     color[v] = 1;
  37.     for (int to: g[v]) {
  38.         if (color[to] == 0) {
  39.             p[to] = v;
  40.             dfs(to);
  41.         } else if (color[to] == 1) {
  42.             add_cycle(v, to);
  43.         }
  44.     }
  45.     color[v] = 0;
  46. }
  47.  
  48. int main() {
  49.     int n=0; cin >> n;
  50.     g.assign(n + 1, vi());
  51.     p.assign(n + 1, 0);
  52.     color.assign(n + 1, 0);
  53.  
  54.     for (int i=1; i<=n; i++) {
  55.         int v=0, u=0; cin >> v >> u;
  56.         g[v].push_back(u);
  57.         g[u].push_back(v);
  58.     }
  59.  
  60.     for (int i=1; i<=n; i++)
  61.         if (color[i] == 0)
  62.             dfs(i);
  63.  
  64.     for (auto cyc: cycle) {
  65.         cout << '\n';
  66.         for (auto v: cyc) cout << v << ' ';
  67.     }
  68. }
  69.  
  70. /*
  71. 5
  72. 1 2
  73. 1 3
  74. 2 3
  75. 2 4
  76. 3 4
  77. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement