Cod sursa(job #2201672)

Utilizator Andreea_DanielaAndreea Guster Andreea_Daniela Data 5 mai 2018 14:53:47
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;

void citire(int &n,vector<int> *&la, ifstream &f){
	int i,x,y;
	f>>n;
 	la=new vector<int>[n+1];
	for(i=1;i<=n-1;i++){
		f>>x>>y;
		la[x].push_back(y);
		la[y].push_back(x);
	}
}


int BF(int s, int n, vector<int> *la, int *tata)
{
	int *viz=new int[n+1]();

	int ultim=0;
	queue<int> c;

	int i;
	tata[s]=0;
	viz[s]=1;
	c.push(s);
	while(!c.empty()){
		int x=c.front();
		ultim=x;//va memora ultimul nod din BF = cel mai departat de s

		c.pop();
		for (i=0;i<la[x].size();i++){
			int y=la[x][i];
			if(viz[y]==0)
				{
					tata[y]=x;
					viz[y] = 1;
					c.push(y);
				}
		}
	}
	return ultim;
}

int main(){
	vector<int> *la;
	int  *tata;
	int n;
	ifstream f("darb.in");
	citire(n,la,f);
	f.close();

    tata=new int[n+1];
	int u=BF(1,n,la,tata); //u va fi extremitatea unui lant elementar maxim

	int v=BF(u,n,la,tata); //lantul de la u la v determinat de BF este maxim

	//diametrul = lungimea lantului de la u la v (!numar de noduri)
	int diam=1;
	int x=v;
	while(x!=u){
		diam++;
		x=tata[x];
	}
	ofstream g("darb.out");
	g << diam;
	g.close();
}