Cod sursa(job #1630300)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 5 martie 2016 00:43:17
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#include <stdlib.h>
#include <time.h>

#define maxN 100001

using namespace std;

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

int n, dist[maxN];
vector <int> Tree[maxN];

void readTree()
{
    int a,b;
    fin>>n;
    while (fin>>a>>b)
    {
        Tree[a].push_back(b);
        Tree[b].push_back(a);
    }
}

void BFS(int &node)
{
    queue <int> Q;
    Q.push(node);
    dist[node]=1;
    while (!Q.empty())
    {
        node=Q.front();
        Q.pop();
        for (int i=0; i<Tree[node].size(); ++i)
        {
            int nb=Tree[node][i];
            if (!dist[nb])
            {
                dist[nb]=dist[node]+1;
                Q.push(nb);
            }
        }
    }
}

int main()
{
    readTree();
    srand(time(NULL));
    int Node = rand() % n + 1;
    BFS(Node);
    fill(dist+1, dist+n+1, 0);
    BFS(Node);
    fout<<dist[Node];
    return 0;
}