Cod sursa(job #2052590)

Utilizator SederfoMarius Vlad Sederfo Data 30 octombrie 2017 19:56:59
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
//#include <iostream> //40pct
//#include <fstream>
//#include <vector>
//#include <queue>
//
//using namespace std;
//
//ifstream fin ("darb.in");
//ofstream fout ("darb.out");
//
//const int Nmax=100000;
//int N, dmax, dist[Nmax+5];
//
//
//vector < int > listaAdiacenta[Nmax+5];
//queue < int > coada;
//
//void Read()
//{
//    fin >> N;
//    for (int i=1; i<=N-1; i++)
//    {
//        int x, y;
//        fin >> x >> y;
//        listaAdiacenta[x].push_back(y);
//        listaAdiacenta[y].push_back(x);
//    }
//    fin.close();
//}
//
//void ClearQueue(queue < int > q)
//{
//    while (!q.empty())
//        q.pop();
//}
//
//void BFS(int nod)
//{
//    ClearQueue(coada);
//    coada.push(nod);
//    for (int i=1; i<=N; i++)
//        dist[i]=-1;
//    dist[nod]=1;
//    while (!coada.empty())
//    {
//        int nodCurent=coada.front();
//        coada.pop();
//        for (int i=0; i<(int)listaAdiacenta[nodCurent].size(); i++)
//        {
//            int vecin=listaAdiacenta[nodCurent][i];
//            if (dist[vecin]==-1)
//                {
//                    dist[vecin]=dist[nodCurent]+1;
//                    if (dist[vecin]>dmax)
//                        dmax=dist[vecin];
//                    coada.push(vecin);
//                }
//        }
//    }
//}
//
//void Print()
//{
//    fout << dmax << "\n";
//}
//
//int main()
//{
//    Read();
//    for (int i=1; i<=N; i++)
//        BFS(i);
//    Print();
//    return 0;
//}
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Nmax=100000;
int N, dmax, dist[Nmax+5], ultimul;

vector < int > listaAdiacenta[Nmax+5];
queue < int > coada;

void Read()
{
    fin >> N;
    for (int i=1; i<=N-1; i++)
    {
        int x, y;
        fin >> x >> y;
        listaAdiacenta[x].push_back(y);
        listaAdiacenta[y].push_back(x);
    }
    fin.close();
}

void BFS(int nod)
{
    coada.push(nod);
    for (int i=1; i<=Nmax+5; i++)
        dist[i]=0;
    dist[nod]=1;
    while (!coada.empty())
    {
        int nodCurent=coada.front();
        coada.pop();
        for (int i=0; i<(int)listaAdiacenta[nodCurent].size(); i++)
        {
            int vecin=listaAdiacenta[nodCurent][i];
            if (dist[vecin]==0)
            {
                dist[vecin]=dist[nodCurent]+1;
                coada.push(vecin);
                dmax=dist[vecin];
                ultimul=vecin;
            }
        }
    }
}

void Rezolvare()
{
    BFS(1);
    BFS(ultimul);
}

void Print()
{
    fout << dmax << "\n";
    fout.close();
}

int main()
{
    Read();
    Rezolvare();
    Print();
}