Advertisement
Guest User

Untitled

a guest
May 21st, 2019
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int maxn = 200005;
  5.  
  6. bool visit[maxn];
  7. vector<int>graph[maxn], curr_graph;
  8. int degree[maxn];
  9.  
  10. void dfs(int u)
  11. {
  12. visit[u] = true;
  13. curr_graph.push_back(u);
  14.  
  15. for(auto v : graph[u])
  16. {
  17. if(!visit[v])
  18. dfs(v);
  19. }
  20. }
  21.  
  22. int countSingleCycles(int n)
  23. {
  24. int cnt = 0;
  25.  
  26. for(int i = 1; i <= n; i++)
  27. {
  28. if(!visit[i])
  29. {
  30. curr_graph.clear();
  31. dfs(i);
  32.  
  33. int flag = 1;
  34. for(auto v: curr_graph)
  35. {
  36. if(degree[v] == 2)continue;
  37. else
  38. {
  39. flag = 0;
  40. break;
  41. }
  42. }
  43. if(flag)cnt++;
  44. }
  45. }
  46. return cnt;
  47. }
  48.  
  49.  
  50. int main()
  51. {
  52. //freopen("in.txt", "r", stdin);
  53. ios_base::sync_with_stdio(false);
  54. cin.tie(0);
  55.  
  56. int n,m;
  57. cin >> n >> m;
  58. for(int i = 0; i < m; i++)
  59. {
  60. int u,v;
  61. cin >> u >> v;
  62. graph[u].push_back(v);
  63. graph[v].push_back(u);
  64. degree[u]++;
  65. degree[v]++;
  66. }
  67. cout << countSingleCycles(n)<<endl;
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement