2716968_wa.cpp

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

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

vector <int> tree[10001];

int n;
int d[10001], heap[10001], visited[10001];

bool cmp(int a,int b)
{
	return d[a]<d[b];
}

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]++;
			heap[i-1] = i - 1;
		}
		r = n-1;scanf("%d",&s);
		make_heap(heap,heap+r,cmp);
		memset(visited,0,sizeof(visited));
		while (r)
		{
			t = heap[0];
			pop_heap(heap,heap+r--,cmp);
			if(!visited[t])
			{
				ans++;
				visited[t] = 1;
				d[t] = 0;
				for (i = 0; i < tree[t].size(); i++)
				{
					if(!visited[tree[t][i]])
					{
						visited[tree[t][i]] = 1;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}