Pagini recente » Cod sursa (job #1006473) | Cod sursa (job #2560324) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #1713635)
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
#include <inttypes.h>
#include <math.h>
#include <vector>
using namespace std;
vector<vector<long> > listaAdj;
vector<long> maxdepth;
vector<long> parinti;
vector<vector<long> > listaAdj2;
long maxim=-1,maxtimp=-1;
void DFS(long parinte,long timp)
{
maxdepth[parinte]=timp;
if(timp>maxtimp)
{
maxtimp=timp;
maxim=parinte;
}
if(listaAdj[parinte].size()==0)
return;
for(long i=0;i<listaAdj[parinte].size();i++)
DFS(listaAdj[parinte][i],timp+1);
}
void DFS2(long parlonge,long grand,long timp) {
maxdepth[parlonge] = timp;
if (timp > maxtimp) {
maxtimp = timp;
maxim = parlonge;
}
for (long i = 0; i < listaAdj2[parlonge].size(); i++)
if(listaAdj2[parlonge][i]!=grand)
DFS2(listaAdj2[parlonge][i],parlonge, timp + 1);
}
int main()
{
fstream f,g;
f.open("darb.in",ios::in);
g.open("darb.out",ios::out);
long n,x,y;
f>>n;
for(int i=0;i<n+1;i++)
maxdepth.push_back(0);
listaAdj=vector<vector<long> >(n+1);
listaAdj2=vector<vector<long> >(n+1);
parinti=vector<long>(n+1,-1);
for(long i=0;i<n-1;i++)
{
f>>x>>y;
listaAdj[x].push_back(y);
listaAdj2[x].push_back(y);
listaAdj2[y].push_back(x);
parinti[y]=x;
}
long parinte=-1;
for(long i=1;i<n;i++)
if(parinti[i]==-1) {
parinte = i;
}
DFS(parinte,0);
for(long i=1;i<n+1;i++)
cout<<maxdepth[i]<<" ";
cout<<endl;
cout<<maxim<<endl;
maxdepth=vector<long>(n,0);
DFS2(maxim,0,0);
cout<<maxim<<endl;
g<<maxim<<endl;
return 0;
}