C++14(g++5.4) 解法, 执行用时: 230ms, 内存消耗: 14720K, 提交时间: 2019-03-09 22:10:29

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>G[maxn];
int cnt,res,low[maxn],dfn[maxn];
void dfs(int u,int fa)
{
	dfn[u]=low[u]=++cnt;
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa)continue;
		if(!dfn[v])
		{
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])
			res++;
		}
		else
		low[u]=min(low[u],dfn[v]);
	}
}
int main()
{
	int n,m,u,v;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	printf("%d\n",m-res);
}

C++11(clang++ 3.9) 解法, 执行用时: 181ms, 内存消耗: 15588K, 提交时间: 2020-01-11 11:06:18

#include<bits/stdc++.h>
using namespace std;

int s=0,c=0,dfn[100005],low[100005];
vector<int>R[100005];
void tarjan(int x,int fa)
{
	int i,j;
	dfn[x]=low[x]=++c;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(!dfn[j])
		{
			tarjan(j,x);
			low[x]=min(low[x],low[j]);
			if(low[j]>dfn[x])s++;
		}
		else if(j!=fa)low[x]=min(low[x],dfn[j]);
	}
}
int main()
{
	int i,j,k,N,M;
	scanf("%d%d",&N,&M);
	for(i=0;i<M;i++)scanf("%d%d",&j,&k),R[j].push_back(k),R[k].push_back(j);
	tarjan(1,0);
	printf("%d\n",M-s);
	return 0;
}