Cod sursa(job #2218318)

Utilizator cucustCucu Stefan cucust Data 4 iulie 2018 11:32:33
Problema Cerere Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMax = 16001;
const int INF = 2e9;
int N;

vector <int> a[NMax];
vector <int> maxim;

bool viz[NMax];
int d[NMax],scor[NMax];

void citire(){
    in>>N;
    int x,y;
    for(int i=1; i<N;i++){
        in>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}


void dfs(int x){

    viz[x]=true;
    int y;
    d[x]=1; scor[x]=0;
    for(int i=0; i<a[x].size(); i++){
        y=a[x][i];
        if(!viz[y]){
            dfs(y);
            d[x]+=d[y];
            scor[x]=max(scor[x],d[y]);
        }
    }
    scor[x] = max(scor[x], N-d[x]);
}
vector <int> pozitii;
int scorMin = INF;
int main()
{
    citire();
    dfs(1);
    for(int i=1;i<=N;i++){
        if(scorMin > scor[i]){
            scorMin = scor[i];
            pozitii.clear();
            pozitii.push_back(i);
        }
        else if(scorMin == scor[i])
            pozitii.push_back(i);
    }
    out<<scorMin<<" "<<pozitii.size()<<'\n';
    for(int i = 0; i<pozitii.size(); i++) out<<pozitii[i]<<" ";
    return 0;
}