Pagini recente » Cod sursa (job #3003129) | Cod sursa (job #285836) | Cod sursa (job #2945990) | Cod sursa (job #1252414) | Cod sursa (job #553687)
Cod sursa(job #553687)
#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;
}