Cod sursa(job #553687)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 14 martie 2011 11:28:02
Problema Salvare Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

int i,j,n,k,ad[1024],fol[1024],admin=2000000,poz,h[4096],rez[1024],l,p,ad1[1024];

vector<int> a[1024];

void dfs(int i)
{
	fol[i]=1;
	
	for(int j=0;j<a[i].size();++j)
	{
		int fiu=a[i][j];
		if(!fol[fiu])
		{
			dfs(fiu);
			if(ad[fiu]+1>ad[i]) ad[i]=ad[fiu]+1;
		}
	}
}

void downheap(int i)
{
	while((ad[h[i]]<ad[h[i*2]]||ad[h[i]]<ad[h[i*2+1]])&&i<l)
	{
		if(ad[h[i]]<ad[h[i*2]])
		{
			int aux=h[i];
			h[i]=h[i*2];
			h[i*2]=aux;
			i*=2;
		}
		
		if(ad[h[i]]<ad[h[i*2+1]])
		{
			int aux=h[i];
			h[i]=h[i*2+1];
			h[i*2+1]=aux;
			i=i*2+1;
		}
		
	}
}

void upheap(int i)
{
	while(i>1&&ad[h[i]]>ad[h[i/2]])
	{
		int aux=h[i];
		h[i]=h[i/2];
		h[i/2]=aux;
		i/=2;
	}
}

void afis(int a[])
{
	for(int i=1;i<=n;++i)
		printf("%d ",a[i]);
	printf("\n");
}

int main()
{
	freopen("salvare.in","r",stdin);
	freopen("salvare.out","w",stdout);
	
	scanf("%d%d",&n,&k);
	
	for(i=1;i<n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	
	for(i=1;i<=n;++i)
	{
		memset(ad,0,sizeof(ad));
		memset(fol,0,sizeof(fol));
		dfs(i);
		p=i;
		
		if(ad[i]<admin)
		{
			admin=ad[i];
			poz=i;
			for(j=1;j<=n;++j) ad1[j]=ad[j];
		}
	}
	memset(fol,0,sizeof(fol));
	
	for(j=1;j<=n;++j) ad[j]=ad1[j];
	
	
	fol[poz]=1;
	h[++l]=poz;
	
	for(i=1;i<=k;++i)
	{
		int nod=h[1];
		h[1]=h[l];
		h[l]=0;
		--l;
		downheap(1);
		rez[nod]=1;
		
		
		for(j=0;j<a[nod].size();++j)
		{
			int fiu=a[nod][j];
			if(!fol[fiu])
			{
				h[++l]=fiu;
				upheap(l);
				fol[fiu]=1;
			}
		}
	}
	
	if(l==0) printf("0\n");
	else printf("%d\n",ad[h[1]]+1);
	
	for(i=1;i<=n;++i)
		if(rez[i]) printf("%d ",i);
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}