WA掉#2 #11

感觉思路比较清晰，先Tarjan标记桥，再去桥缩点建新图，最后加桥记录叶子数（虽然比较麻烦），但不知道哪里错了，哪位大佬能帮帮蒟蒻

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 5010
#define maxm 20010

using namespace std;

inline int read()
{
	int x = 0;
	char c = getchar();
	while(c<'0'||c>'9') {c = getchar();}
	while(c>='0'&&c<='9') {x = (x<<1)+(x<<3)+c-'0'; c = getchar();}
	return x;
}

int n, m, cnt, t;
int color, ans;
int co[maxn]; //新图的点 
int first[maxn];
int head[maxn];
int dfn[maxn];
int low[maxn];
int fa[maxn];  
int leaf[maxn];
bool vis[maxn];
bool mark[maxm]; //标记桥 
struct Node
{
	int from;
	int to;
	int next;
}edge[maxm], e[maxm];

void add(int u, int v)
{
	edge[++cnt].from = u;
	edge[cnt].to = v;
	edge[cnt].next = first[u];
	first[u] = cnt;
}

void Tarjan(int u)
{
	dfn[u] = low[u] = ++t;
	for(int i = first[u]; i; i = edge[i].next)
	{
		int v = edge[i].to;
		if(!dfn[v])
		{
			fa[v] = u; //防止更新成父节点的low 
			Tarjan(v);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u])
			mark[i] = 1; //标记桥 
		}
		else if(v != fa[u])
		low[u] = min(low[u], dfn[v]);
	}
}

void dfs(int x) //缩点 
{
	vis[x] = 1;
	co[x] = color;
	for(int i = first[x]; i&&((!mark[i])&&(!mark[i^1])); i = edge[i].next)
	{
		int y = edge[i].to;
		if(!vis[y]) dfs(y);
	}
}

int main()
{
	n = read(); m = read();
	cnt = 1;
	for(int i = 1; i <= m; i++)
	{
		int u = read();
		int v = read();
		add(u, v);
		add(v, u);
	}
	for(int i = 1; i <= n; i++)
	if(!dfn[i]) Tarjan(i);
	
	for(int i = 1; i <= n; i++) //去掉桥并查集建新图 
	if(!vis[i])
	{
		color++;
		dfs(i);
	}
	
	for(int i = 2; i <= cnt; i++) //加入桥 
	{
		if(!mark[i]) continue;
		int x = edge[i].from;
		int y = edge[i].to;
		leaf[co[x]]++;
		leaf[co[y]]++;
	}

	for(int i = 1; i <= color; i++)
	if(leaf[i] == 1) ans++;
	printf("%d\n", (ans+1)/2);
	
	return 0;
}