Cod sursa(job #1098442)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 4 februarie 2014 20:24:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define dmax 100001
#define pb push_back

int use[dmax], last, maxlvl, Maxl, n;
vector <int> v[dmax];
queue <int> q;

void read()
{
    int a, b;
    scanf("%i", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%i %i", &a, &b);
        v[a].pb(b);
        v[b].pb(a);

    }
}

void BFS(int x)
{
q.push(x);

while(!q.empty())
{x=q.front();
q.pop();
use[x]=1;
for(int i=0;i<v[x].size();i++)
{
    if(use[v[x][i]]==0)
    {
        q.push(v[x][i]);
        use[v[x][i]]=1;
    }

}

}
last=x;
}

void DFS(int x)
{
    use[x]=0;
maxlvl++;
if(maxlvl>Maxl)
    Maxl=maxlvl;
for(int i=0;i<=v[x].size()-1;i++)
{
    if(use[v[x][i]]==1)
    DFS(v[x][i]);
}
maxlvl--;
}

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    read();
BFS(1);


DFS(last);
printf("%i\n", Maxl);

    return 0;
}