Cod sursa(job #1190357)

Utilizator andreiagAndrei Galusca andreiag Data 25 mai 2014 09:52:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
const int Nmax = 100555;

vector<int> G[Nmax];
char used[Nmax];
int dist[Nmax];

int main()
{
    ifstream f ("darb.in");
    ofstream g ("darb.out");

    int N, a, b;
    f >> N;
    for (int i = 0; i < N; i++)
    {
        f >> a >> b;
        //--a;
        //--b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    queue<int> Q;
    int start = 0; //finish = 0;
    Q.push(1);
    used[1] = 1;
    while(!Q.empty())
    {
        int a = Q.front();
        Q.pop();
        start = a;
        for (int b: G[a])
            if (!used[b])
            {
                Q.push(b);
                used[b] = 1;
            }
    }
    
    memset(used, 0, sizeof(used));
    Q.push(start);
    dist[start] = 0;
    int answer = 0;
    used[start] = 1;
    
    while(!Q.empty())
    {
        int a = Q.front();
        answer = dist[a];
        //finish = a;
        Q.pop();
        for (int b: G[a])
            if (!used[b])
            {
                Q.push(b);
                used[b] = 1;
                dist[b] = dist[a] + 1;
            }
    }
    //cout << start << " : " << finish << " = " << answer << '\n';
    g << answer+1 << '\n';

    return 0;
}