牛客算法周周练7 D 华华和月月逛公园（tarjan算法求无向图的割点和桥）

链接：https://ac.nowcoder.com/acm/contest/5713/D
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

月月和华华一起去逛公园了。公园很大，为了方便，可以抽象的看成一个N个点M条边的无向连通图（点是景点，边是道路）。公园唯一的入口在1号点，月月和华华要从这里出发，并打算参观所有的景点。因为他们感情很好，走多远都不会觉得无聊，所以所有景点和道路都可以无数次的重复经过。月月发现，有些路可走可不走，有些路则必须要走，否则就无法参观所有的景点。现在月月想知道，有几条路是不一定要经过的。因为这是个很正常的公园，所以没有重边和自环。

输入描述:

第一行两个正整数N和M，表示点数和边数。
接下来M行，每行两个正整数U和V表示一条无向边。
保证给定的图是连通的。

输出描述:

输出一行一个非负整数表示不一定要经过的边有几条。

示例1

输入

复制5 5 1 2 2 3 3 4 4 5 3 5

5 5
1 2
2 3
3 4
4 5
3 5

输出

复制3

3

说明

例如第三条边，月月和华华可以依次走过第一条、第二条、第五条、第四条边走过全部的景点，所以第三条边不一定要经过。同理还有第四条、第五条边，答案为3。

备注:

1≤N≤1051\le N\le 10^51≤N≤105，1≤M≤3×1051\le M\le 3\times10^51≤M≤3×105

题意：

求连通的无向图中不是必不可少的边

即求不是桥的边数

模板：https://www.cnblogs.com/c1299401227/p/5402747.html

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 3e5 + 5;

vector<int>G[M];
int n, m, low[N], dfn[N];
bool is_cut[N];
int father[N];
int tim = 0;

void input()
{
    scanf("%d%d", &n, &m);
    int a, b;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);/*邻接表储存无向边*/
        G[b].push_back(a);
    }
}

void Tarjan(int i, int Father)
{
    father[i] = Father;/*记录每一个点的父亲*/
    dfn[i] = low[i] = tim++;
    for(int j = 0; j < G[i].size(); ++j)
    {
        int k = G[i][j];
        if(dfn[k] == -1)
        {
            Tarjan(k, i);
            low[i] = min(low[i], low[k]);
        }
        else if(Father != k)/*假如k是i的父亲的话，那么这就是无向边中的重边，有重边那么一定不是桥*/
            low[i] = min(low[i], dfn[k]);//dfn[k]可能！=low[k]，所以不能用low[k]代替dfn[k],否则会上翻过头了。
    }
}

void count()
{
    int rootson = 0;
    Tarjan(1, 0);
    for(int i = 2; i <= n; ++i)
    {
        int v = father[i];
        if(v == 1)
            rootson++;/*统计根节点子树的个数，根节点的子树个数>=2,就是割点*/
        else
        {
            if(low[i] >= dfn[v])/*割点的条件*/
                is_cut[v] = true;
        }
    }
    if(rootson > 1)
        is_cut[1] = true;
//    for(int i = 1; i <= n; ++i)///输出割点
//        if(is_cut[i])
//            printf("%d\n", i);
    int cnt = 0;
    for(int i = 1; i <= n; ++i)///输出桥
    {
        int v = father[i];
        if(v > 0 && low[i] > dfn[v])/*桥的条件*/
//            printf("%d, %d\n", v, i);
            cnt++;
    }
    cout<<m - cnt<<'\n';
}
int main()
{
    input();
    memset(dfn, -1, sizeof(dfn));
    memset(father, 0, sizeof(father));
    memset(low, -1, sizeof(low));
    memset(is_cut, false, sizeof(is_cut));
    count();
    return 0;
}