Codefoces 977E - Cyclic Components——————dfs

我会带着你远行 2022-04-05 08:58 124阅读 0赞

# Cyclic Components #

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.

Here are some definitions of graph theory.

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.

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.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

*  the first vertex is connected with the second vertex by an edge,
 *  the second vertex is connected with the third vertex by an edge,
 *  …
 *  the last vertex is connected with the first vertex by an edge,
 *  all the described edges of a cycle are distinct.

A cycle doesn’t contain any other edges except described above. By definition any cycle contains three or more vertices.  
![6b053ff1e4d04b1dc6db0b6c434db1316c2325ef.png][]

There are 6 connected components, 2 of them are cycles: \[7,10,16\] and \[5,11,9,15\].

### Input ###

The first line contains two integer numbers n and m (1≤n≤2⋅1e5, 0≤m≤2⋅1e5) — number of vertices and edges.

The following m lines contains edges: edge i is given as a pair of vertices vi, ui (1≤vi,ui≤n, ui≠vi). There is no multiple edges in the given graph, i.e. for each pair (vi,ui) there no other pairs (vi,ui) and (ui,vi) in the list of edges.

### Output ###

Print one integer — the number of connected components which are also cycles.

### Examples ###

##### input #####

5 4  
1 2  
3 4  
5 4  
3 5

##### output #####

##### input #####

17 15  
1 8  
1 12  
5 11  
11 9  
9 15  
15 5  
4 13  
3 13  
4 3  
10 16  
7 10  
16 7  
14 3  
14 4  
17 6

##### output #####

### Note ###

In the first example only component \[3,4,5\] is also a cycle.

The illustration above corresponds to the second example.

--------------------

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 2e5+7;
    vector<int> G[MAXN];
    bool vis[MAXN];
    int flag;
    
    void dfs(int x,int fa)
    {
        
    	vis[x] = 1;
    	if(G[x].size()!=2)	flag = 0;
    	for(int i=0;i<G[x].size();++i)
    	{
        
    		int v = G[x][i];
    		if(v==fa||vis[v])	continue;
    		dfs(v,x);
    	}		
    }
    
    int main()
    {
        
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<m;i++)
    	{
        
    		int x,y;
    		cin>>x>>y;
    		G[x].push_back(y);
    		G[y].push_back(x);
    	}
    	memset(vis,0,sizeof(vis));
    	int ans = 0;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(!vis[i])
    		{
        
    			flag = 1;
    			dfs(i,0);
    			if(flag)	ans++;
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
     }

[6b053ff1e4d04b1dc6db0b6c434db1316c2325ef.png]: /images/20220405/4c7706009e8b4916a17aa690611c61e1.png