codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

977E.md (2432B)


      1 Source: https://codeforces.com/problemset/problem/977/E
      2 
      3 E. Cyclic Components
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an undirected graph consisting of $n$ vertices and $m$ edges. Your task is to find the number of connected components which are cycles.
     22 
     23 Here are some definitions of graph theory.
     24 
     25 An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex $a$ is connected with a vertex $b$, a vertex $b$ is also connected with a vertex $a$). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.
     26 
     27 Two vertices $u$ and $v$ belong to the same connected component if and only if there is at least one path along edges connecting $u$ and $v$.
     28 
     29 A connected component is a cycle if and only if its vertices can be reordered in such a way that:
     30 
     31 * the first vertex is connected with the second vertex by an edge,
     32 * the second vertex is connected with the third vertex by an edge,
     33 * ...
     34 * the last vertex is connected with the first vertex by an edge,
     35 * all the described edges of a cycle are distinct.
     36 
     37 A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.
     38 
     39  ![](https://espresso.codeforces.com/2efb48fd56a6167cac3c5a8c51483513d9b48b30.png) There are $6$ connected components, $2$ of them are cycles: $[7, 10, 16]$ and $[5, 11, 9, 15]$.
     40 
     41 Input
     42 
     43 The first line contains two integer numbers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$) — number of vertices and edges.
     44 
     45 The following $m$ lines contains edges: edge $i$ is given as a pair of vertices $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$). There is no multiple edges in the given graph, i.e. for each pair ($v_i, u_i$) there no other pairs ($v_i, u_i$) and ($u_i, v_i$) in the list of edges.
     46 
     47 Output
     48 
     49 Print one integer — the number of connected components which are also cycles.
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 5 4  
     57 1 2  
     58 3 4  
     59 5 4  
     60 3 5
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 17 15  
     73 1 8  
     74 1 12  
     75 5 11  
     76 11 9  
     77 9 15  
     78 15 5  
     79 4 13  
     80 3 13  
     81 4 3  
     82 10 16  
     83 7 10  
     84 16 7  
     85 14 3  
     86 14 4  
     87 17 6
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 2
     94 ```
     95 
     96 Note
     97 
     98 In the first example only component $[3, 4, 5]$ is also a cycle.
     99 
    100 The illustration above corresponds to the second example.