Cod sursa(job #1108575)

Utilizator addy01adrian dumitrache addy01 Data 15 februarie 2014 20:18:45
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define maxn 100010
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int n;
vector <int> Graf[maxn];
queue <int> Q;
int last,ct[maxn],diam;
bool viz[maxn];
void BFS(int nod)
{
    memset(viz,0,sizeof(viz));
    vector <int> :: iterator it;
    Q.push(nod);
    viz[nod]=1;
    ct[nod]=1;
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        for(it=Graf[now].begin();it!=Graf[now].end();it++)
            if(!viz[*it])
            {
                viz[*it]=1;
                ct[*it]=ct[now]+1;
                Q.push(*it);

                diam=ct[*it];
                last=*it;
            }



    }
}

int main()
{
in>>n;
int x,y;
int m=n-1;
while(m--)
{
    in>>x>>y;
    Graf[x].push_back(y);
    Graf[y].push_back(x);
}

BFS(1);
BFS(last);
out<<diam;
    return 0;
}