Pagini recente » Cod sursa (job #109844) | Cod sursa (job #2682521) | Cod sursa (job #2238486) | Cod sursa (job #383953) | Cod sursa (job #2201668)
#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);
}