3042140_ac_944ms_1984k.c

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

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

int n, f, r, m;
int cnt[50005], pos[50005];
int visited[50005], que[50005], pa[50005], god[50005], g;

struct node
{
	int s, e;
}edge[50005*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;
}

int cmp1(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}

void solve()
{
	int i, j, tt;
	int min, minv, 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];
		}
	}
	min = tmp;minv = 1;
	god[0] = 1;g = 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 < min)
		{
			min = tmp;
			god[g = 0] = i;
			g++;
		}
		else
			if(tmp==min)
			{
				god[g++] = i;
			}
	}
	qsort(god,g,4,cmp1);
	for(i = 0; i < g-1; i++)
		printf("%d ",god[i]);
	printf("%d\n",god[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;
}