Cod sursa(job #2589365)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 26 martie 2020 11:23:07
Problema Salvare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define N 1001

using namespace std;

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

vector < int > graph[N];
int d[N], pct[N], l, k, n;
bool viz[N];

void dfs ( int node, int tmp ){
    viz[node] = 1;
    for ( int i = 0; i < graph[node].size ( ); i++ ){
        int new_node = graph[node][i];
        if ( viz[new_node] == 0 ){
            dfs ( new_node, tmp );
            d[node] = max ( d[node], d[new_node] + 1 );
            if ( d[node] == tmp ){
                pct[++l] = node;
                d[node] = -tmp - 1;
            }
        }
    }
}

bool verif ( int tmp ){
    l = 0;
    for ( int i = 1; i <= n; i++ ){
        d[i] = 0;
        viz[i] = 0;
    }
    dfs ( 1, tmp );
    if ( d[1] > 0 )
        pct[++l] = 1;
    if ( l == k )
        return 1;
    return 1;
}

int main()
{   int st, dr, i, x, y, sol;
    f >> n >> k;
    for ( i = 1; i <= n - 1; i++ ){
        f >> x >> y;
        graph[x].push_back ( y );
        graph[y].push_back ( x );
    }
    st = 1, dr = n;
    while ( st <= dr ){
        int mid = ( st + dr ) >> 1;
        if ( verif ( mid ) == 1 ){
            sol = mid;
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }
    g << sol << '\n';
    sort ( pct + 1, pct + k + 1 );
    for ( i = 1; i <= k; i++ )
        g << pct[i] << ' ';
    return 0;
}