Cod sursa(job #1481340)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 4 septembrie 2015 11:25:12
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

#define MAXN 100003
 
int N,viz[MAXN],niv[MAXN],nod_plecare,maxim;;
vector<int> L[MAXN];

void Citire()
{
    int i, x, y;
 
    fin >> N;
    for(i = 1; i < N; i++)
     {  fin >> x >> y; /// citesc noduri
	    L[x].push_back(y);  // actualizez lista de adiacenta
	    L[y].push_back(x);
     }
}

void BFS(int k)
{
	int i,j;
	queue <int> q;
	q.push(k);
	viz[k]=1;
	niv[k]=1;
	
	while (!q.empty())
	{
		k=q.front();
		q.pop();
		
		for (j=0; j<L[k].size(); j++)
		{
			i=L[k][j];
			if (!viz[i])
			   { viz[i]=1;
			     q.push(i);
			     niv[i] = niv[k] + 1;
			     if (niv[i] > maxim)
     	          {   maxim=niv[i];
     	              nod_plecare=i;
	 	          }
			   }
		}
	}
}


void BFS2(int k)
{
	int i,j;
	queue <int> q;
	q.push(k);
	viz[k]=1;
	niv[k]=1;
	while (!q.empty())
	{
		k=q.front();
		q.pop();
		
		for (j=0; j<L[k].size(); j++)
		{
			i=L[k][j];
			if (!viz[i])
			   { viz[i]=1;
			     q.push(i);
			     niv[i] = niv[k] + 1;
			     maxim=max(maxim,niv[i]);
			   }
		}
	}
}

void Rezolva()
{
	int i;
    /// MAI INTAI FACEM O PARCURGERE IN LATIME SI VEDEM UNDE AM AJUNS (NIV[I] = maxim, adica plecam din i)
    BFS(1);
    cout<<nod_plecare;
    maxim=0;
    for (i=1; i<=N; i++)
   {  viz[i]=0; niv[i]=0; }
	BFS2(nod_plecare);
	fout<<maxim<<"\n";
}
 
int main()
{
    Citire();
    Rezolva();
    fin.close();
    fout.close();
    return 0;
}