Guest User

Untitled

a guest
Jun 23rd, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Test {
  4. public static void main(String args[])
  5. {
  6. new Test(new Scanner(System.in));
  7. }
  8.  
  9. Graph g;
  10. int[] deg;
  11. boolean[] used;
  12. int count = 1;
  13. int ans;
  14.  
  15. HashSet<Integer> comp;
  16.  
  17.  
  18. void dfs(int i)
  19. {
  20. used[i] = true;
  21. comp.add(i);
  22.  
  23. for(Edge e : g.adj[i])
  24. {
  25. if(!used[e.j])
  26. dfs(e.j);
  27. }
  28. }
  29.  
  30. Test(Scanner in)
  31. {
  32. g = new Graph(in.nextInt()+1);
  33. used = new boolean[g.N];
  34. deg = new int[g.N];
  35. ans = 0;
  36.  
  37. for(int i=0; i<g.N; i++)
  38. comp = new HashSet<>();
  39.  
  40. int M = in.nextInt();
  41.  
  42. while(M-->0)
  43. {
  44. int i = in.nextInt();
  45. int j = in.nextInt();
  46. g.add(i, j);
  47. }
  48.  
  49. for(int i=1; i<g.N; i++)
  50. if (!used[i]) {
  51. comp.clear();
  52. dfs(i);
  53. boolean ok = true;
  54.  
  55. for(Integer v : comp) ok &= deg[v] == 2;
  56. if (ok) ++ans;
  57. }
  58.  
  59. System.out.printf("%d", ans);
  60. }
  61.  
  62.  
  63. class Graph
  64. {
  65. int N, M;
  66.  
  67. ArrayList<Edge>[] adj;
  68.  
  69.  
  70. Graph(int NN)
  71. {
  72. M = 0;
  73. adj = new ArrayList[N=NN];
  74. for(int i=0; i<N; i++)
  75. adj[i] = new ArrayList<>();
  76. }
  77.  
  78. void add(int i, int j)
  79. {
  80. adj[i].add(new Edge(j, M));
  81. adj[j].add(new Edge(i, M));
  82. ++deg[i];
  83. ++deg[j];
  84. M++;
  85. }
  86. }
  87.  
  88. class Edge
  89. {
  90. int j, id;
  91.  
  92. Edge(int jj, int ii) {
  93. j=jj; id=ii;
  94. }
  95. }
  96. }
Add Comment
Please, Sign In to add comment