Cod sursa(job #2201668)

Utilizator Andreea_DanielaAndreea Guster Andreea_Daniela Data 5 mai 2018 14:50:00
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
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 getVecin(vector<int> v, int *d){
	int i;
	for(i=0;i<v.size();i++)
		if(d[v[i]]!=0)
			return v[i];
	return -1;
}

void elimin(int n,vector<int> *la){
	int i,x,y;
	int *d=new int[n+1];
	queue<int> q;
	for(i=1;i<=n;i++){
		d[i]=la[i].size();
		if(d[i]==1)
			q.push(i);
	}
	int r=0, diam=0;
	if(n==1){
		return;
	}

	while(n>=3){
		int nterm=q.size();
		r++;
		diam+=2;
		for(i=1;i<=nterm;i++){
			x=q.front();
			q.pop();
			d[x]--;
			n--;
			y=getVecin(la[x],d);
		 	d[y]--;
			if(d[y]==1)
				q.push(y);
		}
	}
	ofstream g("darb.out");
	if(q.size()==1)	{
		g << diam +1;
	}
	else{
		g << diam+2;
	}
	g.close();

}

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

    elimin(n,la);



}