Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Test {
- public static void main(String args[])
- {
- new Test(new Scanner(System.in));
- }
- Graph g;
- int[] deg;
- boolean[] used;
- int count = 1;
- int ans;
- HashSet<Integer> comp;
- void dfs(int i)
- {
- used[i] = true;
- comp.add(i);
- for(Edge e : g.adj[i])
- {
- if(!used[e.j])
- dfs(e.j);
- }
- }
- Test(Scanner in)
- {
- g = new Graph(in.nextInt()+1);
- used = new boolean[g.N];
- deg = new int[g.N];
- ans = 0;
- for(int i=0; i<g.N; i++)
- comp = new HashSet<>();
- int M = in.nextInt();
- while(M-->0)
- {
- int i = in.nextInt();
- int j = in.nextInt();
- g.add(i, j);
- }
- for(int i=1; i<g.N; i++)
- if (!used[i]) {
- comp.clear();
- dfs(i);
- boolean ok = true;
- for(Integer v : comp) ok &= deg[v] == 2;
- if (ok) ++ans;
- }
- System.out.printf("%d", ans);
- }
- class Graph
- {
- int N, M;
- ArrayList<Edge>[] adj;
- Graph(int NN)
- {
- M = 0;
- adj = new ArrayList[N=NN];
- for(int i=0; i<N; i++)
- adj[i] = new ArrayList<>();
- }
- void add(int i, int j)
- {
- adj[i].add(new Edge(j, M));
- adj[j].add(new Edge(i, M));
- ++deg[i];
- ++deg[j];
- M++;
- }
- }
- class Edge
- {
- int j, id;
- Edge(int jj, int ii) {
- j=jj; id=ii;
- }
- }
- }
Add Comment
Please, Sign In to add comment