3042150_ac_15ms_500k.c

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n, f, r, m;
int cnt[10005], pos[10005];
int visited[10005], que[10005], pa[10005];

struct node
{
	int s, e;
}edge[10005*2];

int cmp(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;

	return aa->s - bb->s;
}

void solve()
{
	int i, j, tt;
	int tmp;

	f = 1;
	r = 2;
	visited[1] = 1;
	que[1] = 1;
	while(f < r)
	{
		for(i = pos[que[f]]; i < pos[que[f]+1]; i++)
		{
			if(visited[edge[i].e])	continue;
			visited[edge[i].e] = 1;
			que[r] = edge[i].e;
			pa[edge[i].e] = que[f];
			r++;
		}
		f++;
	}
	for(i = n; i > 1; i--)
	{
		cnt[que[i]] ++;
		cnt[pa[que[i]]] += cnt[que[i]];
	}
	cnt[1]++;
	tmp = -1;
	for(j = pos[1]; j < pos[2]; j++)
	{
		if(cnt[edge[j].e] > tmp)
		{
			tmp = cnt[edge[j].e];
		}
	}
	if(tmp <= n/2)
		puts("1");
	for(i = 2; i <= n; i++)
	{
		tmp = -1;
		for(j = pos[i]; j < pos[i+1]; j++)
		{
			if(edge[j].e==pa[i])
			{
				tt = n-cnt[i];
			}
			else
			{
				tt = cnt[edge[j].e];
			}
			if(tt > tmp)
			{
				tmp = tt;
			}
		}
		if(tmp <= n/2)
		{
			printf("%d\n",i);
		}
	}
}

int main()
{
	int i;
	
	memset(cnt,0,sizeof(cnt));
	memset(visited,0,sizeof(visited));
	scanf("%d",&n);
	m = n-1;
	for(i = 1; i <= m; i++)
	{
		scanf("%d%d",&edge[i].s,&edge[i].e);
		edge[i+m].s = edge[i].e;edge[i+m].e = edge[i].s;
	}
	m <<= 1;
	qsort(&edge[1],m,sizeof(edge[1]),cmp);
	for(i = m; i > 0; i--)
	{
		pos[edge[i].s] = i;
	}
	pos[n+1] = m+1;
	solve();
	return 0;
}