2360.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2360 on 2006-11-09 at 19:43:47 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 5120;
 
vector<int> g[N];
int n, bcnt, cnt, dfn[N], low[N];
int stack[N], top, id[N], d[N];
 
void dfs(int, int);
 
int main()
{
	int m;
	
	while(scanf("%d %d", &n, &m) != EOF) {
		for(int i = 0; i < n; i++) g[i].clear();
		for(int i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b); a--; b--;
			g[a].push_back(b); g[b].push_back(a);
		}
		bcnt = cnt = top = 0;
		memset(dfn, -1, sizeof(dfn)); dfs(0, -1);
		memset(d, 0, sizeof(d));
		for(int i = 0; i < n; i++)
			for(int j = g[i].size()-1; j >= 0; j--)
				if(id[i] != id[g[i][j]]) { d[id[i]]++; d[id[g[i][j]]]++; }
		int leafn = 0;
		for(int i = 0; i < bcnt; i++)
			if(d[i] == 2) leafn++;
		printf("%d\n", (leafn+1)>>1);
	}
	
	return 0;
}
 
void dfs(int o, int p)
{
	int pcnt = 0;
	int h = dfn[o] = low[o] = cnt++;
	stack[top++] = o;
	for(int i = g[o].size()-1; i >= 0; i--) {
		int no = g[o][i];
		if(no == p) { pcnt++; continue; }
		else if(dfn[no] == -1) dfs(no, o);
		h <?= low[no];
	}
	if(pcnt > 1) h <?= dfn[p];
	if(h == low[o]) {
		int k;
		do {
			k = stack[--top];
			id[k] = bcnt;
		} while(k != o);
		bcnt++;
	}
	low[o] = h;
}