Cod sursa(job #1890176)

Utilizator stanciuandreiStanciulescu Andrei stanciuandrei Data 23 februarie 2017 09:35:48
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
/*
    Diametrul unui arbore
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define MAXN 100000 + 4

using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");
vector<int> graph[MAXN];
queue<int> coada;
queue<int> depth;
bool visited[MAXN];

int n, x, y, ff, maxdist;

void bfs(int start){
    memset(visited, 0, sizeof(visited));
    while(!coada.empty())
        coada.pop();
    coada.push(start);
    depth.push(1);
    while(!coada.empty()){
        if(depth.front()>maxdist){
            maxdist = depth.front();
            ff = coada.front();
        }
        for(unsigned int i=0;i<graph[coada.front()].size();i++){
            if(!visited[graph[coada.front()][i]]){
                visited[graph[coada.front()][i]] = 1;
                coada.push(graph[coada.front()][i]);
                depth.push(depth.front()+1);
            }
        }
        coada.pop();
        depth.pop();
    }
}

int main()
{
    in>>n;
    for(int i=0;i<n;i++){
        in>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    bfs(1);
    bfs(ff);
    out<<maxdist;
    return 0;
}