Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 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, ncycle = 0;
  10.  
  11. vi p, color; // parents, color
  12. vvi cycle, g; // all cycles, graph
  13.  
  14. int add_cycle(int cycle_end, int cycle_st) {
  15.     // очистить, так как мог быть сохранен не цикл
  16.     cycle[ncycle].clear();
  17.  
  18.     // через предков восстановить цикл
  19.     cycle[ncycle].push_back(cycle_st);
  20.     for (int v=cycle_end; v!=cycle_st; v=p[v])
  21.         cycle[ncycle].push_back(v);
  22.     cycle[ncycle].push_back(cycle_st);
  23.  
  24.     reverse(cycle[ncycle].begin(), cycle[ncycle].end());
  25.     return cycle[ncycle].size();
  26. }
  27.  
  28. void dfs(int v) {
  29.     color[v] = 1;
  30.     for (int to: g[v]) {
  31.         if (color[to] == 0) {
  32.             p[to] = v;
  33.             dfs(to);
  34.         } else if (color[to] == 1) {
  35.             // неориентированный граф
  36.             // избавляюсь от вырожденности (v - to - v)
  37.             if (add_cycle(v, to) > 3)
  38.                 ncycle++;
  39.         }
  40.     }
  41.     color[v] = 0;
  42. }
  43.  
  44. int main() {
  45.     int n=0; cin >> n;
  46.     g.assign(n + 1, vi());
  47.     cycle.assign(n + 1, vi());
  48.     color.assign(n + 1, 0);
  49.  
  50.     for (int i=1; i<=n; i++) {
  51.         int v=0, u=0; cin >> v >> u;
  52.         g[v].push_back(u);
  53.         g[u].push_back(v);
  54.     }
  55.  
  56.     for (int i=1; i<=n; i++)
  57.         if (color[i] == -1)
  58.             dfs(i);
  59.  
  60.     cout << endl << ncycle << endl;
  61. }
  62.  
  63. /*
  64. 5
  65. 1 2
  66. 1 3
  67. 2 3
  68. 2 4
  69. 3 4
  70. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement