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

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

复制

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

输出

复制

3

说明

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

备注:

1≤N≤105

题意：求割边

题解：用tarjin求一下割边就行了，参考

#include <bits/stdc++.h>
#define maxn 100000+5
using namespace std;
struct node {
    int u,v;
};
int id,low[maxn],dfn[maxn];
int n,m;
vector<int>G[maxn];
vector<node>ans;node e;
void tarjin(int u,int dad){
    low[u]=dfn[u]=++id;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==dad)continue;
        if(!dfn[v]){
            tarjin(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                e.u=u;
                e.v=v;
                ans.push_back(e);
            }
        }else low[u]=min(low[u],dfn[v]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&e.u,&e.v);
        G[e.u].push_back(e.v);
        G[e.v].push_back(e.u);
    }
    for(int i=1;i<n;i++){
        if(!dfn[i]){
            tarjin(i,i);
        }
    }
    cout<<m-ans.size()<<endl;
    //while(1)getchar();
    return 0;
}

附上求割点的代码

void tarjan(int u, int root)
{
    int child = 0;
    dfn[u] = low[u] = ++id;
    for (size_t i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (dfn[v] == 0) {
            tarjan(v, root);
            low[u] = min(low[u], low[v]);//为能访问的最原始祖先
            if (u != root && low[v] >= dfn[u]) cut[u] = true;//如果某点必须通过这个点访问它或者它的祖先  这个点是割点
            if(low[v]>dfn[u]) bridge[u]=1;//割边
            if (u == root) child++;//点的孩子加
        }
        low[u] = min(low[u], dfn[v]);//这个点所能到达的最大祖先
    }
    if (u == root && child >= 2) cut[root] = true;//如果是根节点，并且不是一个孩子，那么是割点
}