Cod sursa(job #1921383)

Utilizator SanteCiolosSante Ciolos SanteCiolos Data 10 martie 2017 12:29:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

#define N 100001

using namespace std;

void citire();
void BFS(int x);

vector<int> A[N];
queue<int> C;
int n, l, d;
int contor[N];
bool viz[N];


int main()
{
    ofstream out("darb.out");
    citire();
    BFS(1);
    BFS(l);
    out << d << endl;
    return 0;
}

void citire()
{
    ifstream in("darb.in");
    int x, y;

    in >> n;

    while(in >> x >> y)
    {
        A[x].push_back(y);
        A[y].push_back(x);
    }
}

void BFS(int x)
{
    memset(contor, 0, N);
    memset(viz, 0, N);

    C.push(x);
    contor[x] = 1;
    viz[x] = true;

    while(!C.empty())
    {
        x = C.front();
        C.pop();

        for(int i = 0; i < A[x].size(); i++)
        {
            if(!viz[A[x][i]])
            {
                C.push(A[x][i]);
                viz[A[x][i]] = true;
                contor[A[x][i]] = contor[x] + 1;

                d = contor[A[x][i]];
                l = A[x][i];
            }
        }
    }
}