Mai intai trebuie sa te autentifici.
Cod sursa(job #1116909)
Utilizator | Data | 22 februarie 2014 21:39:02 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.48 kb |
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#define NMax 100001
using namespace std;
list<int> v[NMax];
list<int>::iterator it;
int n, a, b, c;
vector<bool> viz;
void bf(int from){
viz=vector<bool>(n+1, false);
queue<int> coada;
coada.push(from);
int crt;
do{
a=crt=coada.front();
coada.pop();
//cout<<crt<<" ";
viz[crt]=true;
for(it=v[crt].begin(); it!=v[crt].end(); it++)
if(!viz[*it])
coada.push(*it);
}while(!coada.empty());
}
void dfStack(int from){
viz=vector<bool>(n+1, false);
stack<int> stiva;
stiva.push(from);
int crt;
do{
b=crt=stiva.top();
stiva.pop();
//cout<<crt<<" ";
viz[crt]=true;
for(it=v[crt].begin(); it!=v[crt].end(); it++)
if(!viz[*it])
stiva.push(*it);
}while(!stiva.empty());
}
void dfRecursive(int crt, int step){
viz[crt]=true;
b=max(step, b);
for(list<int>::iterator it2=v[crt].begin(); it2!=v[crt].end(); it2++)
if(!viz[*it2])
dfRecursive(*it2, step+1);
}
int main(){
ifstream f("darb.in");
f>>n;
for(int i=1;i<n;i++)
f>>a>>b,
v[a].push_back(b),
v[b].push_back(a);
bf(1);
viz=vector<bool>(n+1, false); b=0;
dfRecursive(a, 0);
ofstream g("darb.out");
g<<(b+1)<<"\n";
return 0;
}