Cod sursa(job #912277)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 12 martie 2013 11:14:44
Problema Salvare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in ("salvare.in");
ofstream out ("salvare.out");

const int N = 1001;

vector<int> G[N],V;
int n,k,SOL;

void READ (void)
{

    in>>n>>k;

    for( int x,y,i=1 ; i < n ; ++i )
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

}

void SOLVE (void)
{

    int m=n-k;

    vector<int> D(n+1,n);

    for( int i=1 ; i <= m ; ++i )
    {
        int d=N,I;
        for( int j=1 ; j <= n ; ++j )
            if( G[j].size() == 1 )
            {
                if( D[j] == n )
                    D[j]=0;
                if( D[j] < d )
                d=D[j];
                I=j;
            }
        int T=G[I].back();
        G[I].pop_back();
        D[T]=min(D[T],D[I]+1);
        for( vector<int>::iterator it=G[T].begin() ; it < G[T].end() ; ++it )
            if( *it == I )
            {
                G[T].erase(it);
                break;
            }
    }
    for( int i=1 ; i <= n ; ++i )
        if( D[i] )
        {
            SOL=max(SOL,D[i]);
            V.push_back(i);
        }

}

void PRINT (void)
{

    out<<SOL<<'\n';

    for( vector<int>::iterator it=V.begin() ; it < V.end() ; ++it )
        out<<(*it)<<' ';

}

int main (void)
{

    READ ( );
    SOLVE ( );
    PRINT ( );

}