Pagini recente » Cod sursa (job #3218569) | Cod sursa (job #1448930) | Cod sursa (job #660575) | Cod sursa (job #2356152) | Cod sursa (job #2201661)
#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);
//neorientat
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;
for(i=1;i<=n;i++)
viz[i]=0;
tata[s]=0;
viz[s]=1;
c.push(s);
while(!c.empty()){
int x=c.front();//x- nodul curent
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];//pentru toti vecinii y ai nodului curent x
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 muchii)
int diam=0;
int x=v;
while(x!=u){
diam++;
x=tata[x];
}
ofstream g("darb.out");
g << diam;
g.close();
}