Cod sursa(job #1641090)

Utilizator CnemusTudor Luca Ioan Cnemus Data 8 martie 2016 20:54:03
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#define LIM 200000
using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

int n,m,M,a,b;
int seen[LIM];

struct G{
    list <int> edge;
}graph[LIM];

void read(){
    in>>n;
    m=n-1;
    int x,y;
    for(int i=0;i<m;i++){
        in>>x>>y;
        graph[x].edge.push_back(y);
        graph[y].edge.push_back(x);
    }
}

void BFS(int vertex){
    if(seen[vertex]>1) return;
    queue<int> c,g;
    c.push(vertex);
    g.push(0);
    while(!c.empty()){
        a=c.front();
        b=g.front();
        seen[a]++;
        for(list<int>::iterator it=graph[a].edge.begin();it!=graph[a].edge.end();++it)
            if(seen[*it]==seen[a]-1){
                c.push(*it);
                g.push(++b);
            }
        c.pop();
        g.pop();
    }
}

void diametre (){
    for(int i=1;i<=n;i++){
        BFS(i);
        BFS(a);
        if(b>M) M=b;
    }
}

int main()
{
    read();
    diametre();
    out<<M;

    return 0;
}