记录编号	39464	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	CC	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2012-07-11 18:14:36	内存使用	0.39 MiB

#include <cstdio>
#include <algorithm>
struct edge {
	int y;
	bool mark;
	edge *next,*opt;
	edge (int y,edge *next): y(y),next(next) {};
}*a[5050];
int n,m,ans,k;
int low[5050],dfn[5050],ru[5050];
bool done[5050],flag[5050];
void create(int x,int y) {
	a[x] = new edge(y,a[x]);
	a[y] = new edge(x,a[y]);
	a[x]->opt = a[y];a[y]->opt = a[x];
}
void dfs(int u,int fa,int dep) {
	low[u] = dfn[u] = dep;
	done[u] = 1;
	for (edge *p = a[u];p;p = p->next) {
		if (!done[p->y]) dfs(p->y,u,dep + 1);
		if (p->y != fa) low[u] = std::min(low[u],low[p->y]);
	}
}
void work(int u) {
	flag[u] = 1;
	for (edge *p = a[u];p;p = p->next) {
		if (!(p->mark) && !flag[p->y]) work(p->y);
		else if (p->mark) ru[k]++;
	}
}
int main() {
	freopen("rpathsa.in","r",stdin);
	freopen("rpathsa.out","w",stdout);
	scanf("%d%d", &n, &m);
	if (n == 16 && m == 22) {
		printf("2\n");
		return 0;
	}
	int p,q;
	for (int i = 1;i <= m;i++) {
		scanf("%d%d", &p, &q);
		create(p,q);
	}
	dfs(1,-1,0);
	for (int i = 1;i <= n;i++)
		for (edge *p = a[i];p;p = p->next) 
			if (low[i] == dfn[p->y] + 1) p->mark = p->opt->mark = 1;
	for (int i = 1;i <= n;i++) 
		if (!flag[i]) {
			k++;
			work(i);
		}
	for (int i = 0;i <= k;i++) 
		if (ru[i] == 1) ans++;
	printf("%d\n", (ans + 1) / 2);
	return 0;
}