CF Round 479 (Div. 3)--E. Cyclic Components(DFS求无向图中独立环的个数)

这篇具有很好参考价值的文章主要介绍了CF Round 479 (Div. 3)--E. Cyclic Components(DFS求无向图中独立环的个数)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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.

CF Round 479 (Div. 3)--E. Cyclic Components(DFS求无向图中独立环的个数),深度优先,算法,c++,c语言

 

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⋅10^5, 0≤m≤2⋅10^5) — 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≠v). 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.

input

5 4
1 2
3 4
5 4
3 5

output

1

题意:就是n个点,m条无向边,让你求出其中独立环的个数(环与环没有交集,且环没有其他无用边)。

解析:我们可以发现,对于一个合法环,环上每个点一定都连出去两条边,我们可以对于每一个没搜过的点,进行DFS,中间判断是否合法,如果到最后搜回来这个点,那么说明是一个环,如此计数即可。文章来源地址https://www.toymoban.com/news/detail-697731.html

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int> v[N];
int cnt;
bool st[N],ok;
void dfs(int u,int fa)
{
    if(ok) return;//已经找到了
    if(st[u])
    {
        cnt++;//环的个数+1
        ok=true;
        return;
    }
    st[u]=true;
    for(int i=0;i<v[u].size();i++)
    {
        int j=v[u][i];//子节点
        if(j==fa||v[j].size()!=2) continue;//避免回搜
        dfs(j,u);
    }
}
void solve()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if(st[i]||v[i].size()!=2) continue;//如果已经被访问过或者不可能是环,直接不用进行
        ok=false;
        dfs(i,i);
    }
    printf("%d\n",cnt);
}
int main()
{
    int t=1;
    //scanf("%d",&t);
    while(t--) solve();
    return 0;
}

到了这里,关于CF Round 479 (Div. 3)--E. Cyclic Components(DFS求无向图中独立环的个数)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode:1402. 做菜顺序、2316. 统计无向图中无法互相到达点对数

    1. 1402 做菜顺序 题目详细为: 一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。 一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间(包含之前每道菜所花费的时间)乘以这道菜的满意程度,也就是 time[i]*satisfaction[i] 。 返回

    2024年01月23日
    浏览(35)
  • cf-920-div3

    题目大意 给出四个坐标点,求正方形面积 解题思路 最小的最小,最大的最大。 代码实现 题目大意 有三种操作,求字符串 s s s 变成字符串 t t t 的最少次数 解题思路 显然,相同的不变,只需要对不同的进行操作,统计两个字符串的 1 1 1 的数量,取最多。 代码实现 题目大意

    2024年01月19日
    浏览(39)
  • 【枚举+trie+dfs】CF514 C

    Problem - 514C - Codeforces 题意:   思路: 其实是trie上dfs的板题 先把字符串插入到字典树中 对于每次询问,都去字典树上dfs 注意到字符集只有3,因此如果发现有不同的字符,去枚举新的字符 Code:

    2024年02月14日
    浏览(34)
  • 【简单图论】CF898 div4 H

    Problem - H - Codeforces 题意: 思路: 手玩一下样例就能发现简单结论: v 离它所在的树枝的根的距离 m 离这个根的距离时是 YES 否则就是NO 实现就很简单,先去树上找环,然后找出这个根,分别给a 和 b BFS一遍,得出两个dis数组,比较一下即可 对于只有的环情况 和 m = v 的情况需

    2024年02月07日
    浏览(48)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(54)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(43)
  • Codeforces Round 920 (Div. 3)

    Codeforces Round 920 (Div. 3) 题意:随机给出正方形在平面坐标系上的四个顶点的坐标,求正方形的面积,正方形边与xy轴平行。 思路:因为正方形与坐标轴平行,所以找出相同的两x或y坐标即可找到一条边的长度,平方就是面积,注意结果返回整型。 AC code: 题意:给出两个01字符

    2024年01月17日
    浏览(55)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(36)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(43)
  • Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串,问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组,问连续相邻为0的最大长度 维护一个全局最大长度res,和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包