2717297_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;

vector <int> tree[10001];
queue <int> que;
int n;
int d[10001], visited[10001];

int main()
{
	int i, r;
	int a, b;
	int ans, t, s = 0;

	while (!s&&scanf("%d",&n)==1)
	{
		ans = 0;
		memset(d,0,sizeof(d));
		for (i = 0; i < n; i++)
			tree[i].clear();
		for (i = 1; i < n; i++)
		{
			scanf("%d%d",&a,&b);
			a--,b--;
			tree[a].push_back(b);
			tree[b].push_back(a);
			d[a]++;d[b]++;
		}
		for (i = 0; i < n; i++)
			if (d[i]==1)
				que.push(i);
		memset(visited,0,sizeof(visited));
		while (!que.empty())
		{
			t = que.front();
			que.pop();
			if (d[t]!=1)
			{
				continue;
			}
			r = tree[t][0];
			/*if (visited[t])
				continue;
			for (i = 0; i < tree[r].size(); i++)
			{
				d[tree[r][i]]--;
				d[t]--;
			}*/
			d[r] = 0;ans++;
			for (i = 0; i < tree[r].size(); i++)
			{
				d[tree[r][i]]--;
				if (d[tree[r][i]]==1)
					que.push(tree[r][i]);
			}
		}
		printf("%d\n",ans);
		scanf("%d",&s);
	}
	return 0;
}