链接：https://ac.nowcoder.com/acm/contest/392/I?&headNav=acm 来源：牛客网
时间限制：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
输出
复制
3
说明
例如第三条边，月月和华华可以依次走过第一条、第二条、第五条、第四条边走过全部的景点，所以第三条边不一定要经过。同理还有第四条、第五条边，答案为3。
备注:
1≤N≤1051≤N≤105，1≤M≤3×105
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=3e5+10;
struct edge
{
int v,next;
}e[M*2];
int head[N],dfn[N],low[N];
bool vis[M*2];
int n,m;
int cnt,inde;
void add(int x,int y)
{
e[cnt]=(edge){y,head[x]};head[x]=cnt++;
e[cnt]=(edge){x,head[y]};head[y]=cnt++;
}
int ans=0;
stack<int>que;
void tarjan(int root)
{
dfn[root]=low[root]=++inde;
que.push(root);
for(int i=head[root];i!=-1;i=e[i].next)
{
if(vis[i]) continue;
vis[i]=vis[i^1]=1;
int v=e[i].v;
if(!dfn[v])
{
tarjan(v);
low[root]=min(low[root],low[v]);
if(dfn[root]<low[v]) ans++;
/*
if(dfn[root]<=low[v]&&v!=fa) ans1++;//割顶的个数 fa是根节点，第一个点出发的
*/
}
else
{
low[root]=min(low[root],dfn[v]);
}
}
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
printf("%d\n",m-ans);
}
