Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Borderou de evaluare (job #2197943) | Cod sursa (job #1452973) | Cod sursa (job #1713625)
#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<int> > listaAdj;
vector<int> maxdepth;
vector<int> parinti;
vector<vector<int> > listaAdj2;
int maxim=-1,maxtimp=-1;
void DFS(int parinte,int timp)
{
maxdepth[parinte]=timp;
if(timp>maxtimp)
{
maxtimp=timp;
maxim=parinte;
}
if(listaAdj[parinte].size()==0)
return;
for(int i=0;i<listaAdj[parinte].size();i++)
DFS(listaAdj[parinte][i],timp+1);
}
void DFS2(int parinte,int grand,int timp) {
maxdepth[parinte] = timp;
if (timp > maxtimp) {
maxtimp = timp;
maxim = parinte;
}
for (int i = 0; i < listaAdj2[parinte].size(); i++)
if(listaAdj2[parinte][i]!=grand)
DFS2(listaAdj2[parinte][i],parinte, timp + 1);
}
int main()
{
fstream f,g;
f.open("darb.in",ios::in);
g.open("darb.out",ios::out);
int n,x,y;
f>>n;
maxdepth=vector<int>(n,0);
listaAdj=vector<vector<int> >(n+1);
listaAdj2=vector<vector<int> >(n+1);
parinti=vector<int>(n+1,-1);
for(int 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;
}
int parinte=-1;
for(int i=1;i<n;i++)
if(parinti[i]==-1) {
parinte = i;
}
DFS(parinte,0);
for(int i=1;i<n+1;i++)
cout<<maxdepth[i]<<" ";
cout<<endl;
cout<<maxim<<endl;
maxdepth=vector<int>(n,0);
DFS2(maxim,0,0);
cout<<maxim<<endl;
g<<maxim<<endl;
}