我是靠谱客的博主 寂寞马里奥,这篇文章主要介绍E. 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.

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 ( 1n2105, 0m2105

) — number of vertices and edges.

The following m

lines contains edges: edge i is given as a pair of vertices vi, ui ( 1vi,uin, uivi). 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
复制代码
1
2
3
4
5
5 4 1 2 3 4 5 4 3 5
Output
复制代码
1
1
Input
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
复制代码
1
2
Note

In the first example only component [3,4,5]

is also a cycle.

The illustration above corresponds to the second example.

题意:给你n个点,m条边,问其中环的个数

分析:1、环的定义是每个点的度为二,也就是不能有多余的分支

            2、dfs找到同一个集合的点,然后判断所有点的度是否为2,来判断是否成环

           3、判断点的度可以用邻接表中每个点对应的大小

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; #include <vector> vector<int> g[200010]; vector<int> di; int vis[200010]={0}; void dfs(int x) //找到同一个集合的点 { vis[x]=1; //避免重复查找 di.push_back(x); //存储同一个集合的点 for(int i=0;i<g[x].size();i++) //遍历对应的邻接表 { if(vis[g[x][i]]==0) dfs(g[x][i]); } } int main() { int n,m,x,y,i,j,cnt=0; scanf("%d%d",&n,&m); for(i=0;i<m;i++) { scanf("%d%d",&x,&y); g[x].push_back(y); //存储邻接表 g[y].push_back(x); } for(i=1;i<=n;i++) { if(!vis[i]) { di.clear(); //清空存储仓 dfs(i); for(j=0;j<di.size();j++) //判断是否成环,所有点的度均为2 { if(g[di[j]].size()!=2) break; } if(j==di.size()) cnt++; } } printf("%dn",cnt); return 0; }

最后

以上就是寂寞马里奥最近收集整理的关于E. Cyclic Components的全部内容,更多相关E.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(73)

评论列表共有 0 条评论

立即
投稿
返回
顶部