Cod sursa(job #2659614)

Utilizator kerry6205Motiu Radu kerry6205 Data 17 octombrie 2020 11:07:47
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

vector<vector<int> > G;
vector<int> viz;
queue<int> Q;
int N, x, y, nodfinal, l;

void citire()
{
    fin >> N;
    G.resize(N + 1);
    for(int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        G[y].push_back(x);
        G[x].push_back(y);
    }
}

void DFS(int z, int &l)
{
    viz[z] = 1;
    nodfinal = z;
    l++;
    for(int i = 0; i < G[z].size(); i++)
        if(!viz[G[z][i]])
            DFS(G[z][i], l);
}

void BFS(int z)
{
    Q.push(z);
    viz[z] = 1;
    while(!Q.empty())
    {
        int Nod = Q.front();
        //cout << Nod << ' ';
        for(int i = 0; i < G[Nod].size(); i++)
        {
            int Vecin = G[Nod][i];
            if(!viz[Vecin])
            {
                viz[Vecin] = viz[Nod] + 1;
                l = viz[Vecin];
                nodfinal = Vecin;
                //cout << l << endl;
                Q.push(Vecin);
            }
        }
        Q.pop();
    }
}

int main()
{
    citire();
    viz.resize(N + 1);
    //int l = 0;
    BFS(1);
    //for(int i = 0; i < viz.size(); i++)
       //cout << viz[i] << ' ';
    //cout << l;
    viz.clear();
    viz.resize(N + 1);
    BFS(nodfinal);
    //cout << nodfinal;
    fout << l;
    //for(int i = 0; i < viz.size(); i++)
     // cout << viz[i];
}