Pagini recente » Cod sursa (job #2657300) | Cod sursa (job #2978125) | Cod sursa (job #3206757) | Cod sursa (job #503360) | Cod sursa (job #2157226)
#include <bits/stdc++.h>
std::ifstream in("salvare.in");
std::ofstream out("salvare.out");
using namespace std;
const int MAX = 1002;
int oo = ( 1 << 30);
int D[MAX];
struct Node
{
int n,distance;
bool operator < (const Node &a ) const
{
return distance > a.distance;
}
}N[MAX];
bitset < MAX > beenThere;
vector < int > myVector[MAX];
struct CMP
{
bool operator() ( int x , int y)
{
return D[x] > D[y];
}
};
priority_queue < int , vector < int > ,CMP > myQueue;
int numberOfNodes, Saves;
inline void scanDATA()
{
in >> numberOfNodes >> Saves;
for ( int i = 1; i <= numberOfNodes-1 ; ++i)
{
int x,y;
in >> x >> y;
myVector[x].push_back(y);
myVector[y].push_back(x);
}
for ( int i = 1 ; i <= numberOfNodes ; ++i)
{
if( myVector[i].size() == 1)
{
myQueue.push(i);
beenThere[i] = true;
D[i] = 0;
}
else D[i] = oo;
}
}
int main()
{
scanDATA();
while(!myQueue.empty())
{
int currentNode = myQueue.top();
myQueue.pop();
beenThere[currentNode] = false;
for ( auto x : myVector[currentNode])
{
if(D[currentNode]+1 < D[x])
{
D[x] = D[currentNode]+1;
if(!beenThere[x])
{
beenThere[x] = true;
myQueue.push(x);
}
}
}
}
for ( int i = 1; i <= numberOfNodes ; ++i)
{
N[i].n = i;
N[i].distance = D[i];
}
sort (N+1 , N+numberOfNodes+1);
out << N[1].distance <<"\n";
for ( int i = 1 ; i <= Saves ; ++i)
out << N[i].n <<" ";
}