Cod sursa(job #1488241)

Utilizator serbanSlincu Serban serban Data 18 septembrie 2015 11:22:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

vector< int > v[100005];
queue< int > q;

int n;
bool viz[100005];
int last, ret;
int d[100005];

void bfs(int in) {
    for(int i = 0; i <= n; i ++)
        d[i] = 0, viz[i] = false;
    q.push(in);
    viz[in] = true;
    d[in] = 1;
    while(!q.empty()) {
        in = q.front();
        int i;
        for(i = 0; i != v[in].size() ; i ++) {
            int x = v[in][i];
            if(viz[x] == 0) {
                q.push(x);
                d[x] = d[in] + 1;
                viz[x] = true;
                last = x;
                ret = d[x];
            }
        }
        q.pop();
    }
}

int main()
{
    FILE *f = fopen("darb.in", "r");
    FILE *g = fopen("darb.out", "w");

    fscanf(f, "%d" , &n);
    for(int i = 1; i <= n; i ++) {
        int a, b;
        fscanf(f, "%d %d" , &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(1);
    bfs(last);
    fprintf(g, "%d\n", ret);
    return 0;
}