Cod sursa(job #1239209)

Utilizator lorundlorund lorund Data 8 octombrie 2014 15:57:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <vector>
#include <bitset>
#define SIZE 100005
using namespace std;

int n, last;
bitset<SIZE> vis;
vector<int> graph[SIZE];

int bfs(int node){
    vector< pair<int, int> > que;
    vis.reset();

    que.push_back(make_pair(node, 0));
    vis[node] = 1;
    for (unsigned i=0; i<que.size(); ++i){
        last = que[i].first;
        for (unsigned p=0; p<graph[last].size(); ++p){
            if (!vis[graph[last][p]]){
                vis[graph[last][p]] = 1;
                que.push_back(make_pair(graph[last][p], que[i].second+1));
            }

        }
    }

    return que.back().second;
}

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

    scanf("%d", &n);
    for (int i=1; i<n; ++i){
        int x, y;

        scanf("%d %d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    bfs(1);
    printf("%d", bfs(last)+1);
    return 0;
}