Pagini recente » Cod sursa (job #1441163) | Cod sursa (job #1139781) | Cod sursa (job #339013) | Cod sursa (job #982951) | Cod sursa (job #2390127)
#include <cstdio>
#include <bitset>
#include <vector>
#include <algorithm>
#include <deque>
#define DIMN 1001
using namespace std;
int elem,salv[DIMN],d[DIMN],k,n,root,grad[DIMN];
bitset <DIMN> f;
vector <int> v[DIMN];
deque <int> dq;
void dfs (int nod,int x){
int i,vecin;
f[nod]=1;
if (nod!=root && v[nod].size()==1){ /// frunza
d[nod]=x;
return;
}
d[nod]=2*x+1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (f[vecin]==0){
dfs(vecin,x);
d[nod]=min(d[nod],d[vecin]-1);
}
}
if (d[nod]<=0){ /// nod marcat
d[nod]=2*x+1;
salv[++elem]=nod;
}
}
int verif (int x){
int i,vecin,nod;
elem=0;
for (i=1;i<=n;i++){
d[i]=2000000000;
grad[i]=v[i].size();
if (grad[i]==1){
d[i]=x;
dq.push_back(i);
}
}
while (!dq.empty()){
nod=dq.front();
//if (x==1)
//printf ("%d %d\n",nod,d[nod]);
if (d[nod]==0){
d[nod]=2*x+1;
salv[++elem]=nod;
}
dq.pop_front();
if (grad[nod]==0){
if (d[nod]<=x)
salv[++elem]=nod;
}
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
grad[vecin]--;
if (grad[vecin]>=1)
d[vecin]=min(d[vecin],d[nod]-1);
if (grad[vecin]==1){
dq.push_back(vecin);
}
}
}
if (elem<=k)
return 1;
return 0;
}
int main()
{
FILE *fin=fopen ("salvare.in","r");
FILE *fout=fopen ("salvare.out","w");
int i,x,y,st,dr,mid,add,p;
fscanf (fin,"%d%d",&n,&k);
for (i=1;i<n;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
if (k==n){
fprintf (fout,"0\n");
for (i=1;i<=n;i++)
fprintf (fout,"%d ",i);
return 0;
}
st=1;
dr=n;
while (st<=dr){
mid=(st+dr)/2;
if (verif (mid))
dr=mid-1;
else st=mid+1;
}
verif (st);
fprintf (fout,"%d\n",st);
f.reset();
for (i=1;i<=elem;i++)
f[salv[i]]=1;
add=k-elem;
p=1;
while (add){
if (!f[p]){
salv[++elem]=p;
add--;
}
p++;
}
sort (salv+1,salv+elem+1);
for (i=1;i<=elem;i++)
fprintf (fout,"%d ",salv[i]);
return 0;
}