Pagini recente » Cod sursa (job #2701266) | Cod sursa (job #1146583) | Cod sursa (job #1944297) | Cod sursa (job #2494195) | Cod sursa (job #1666663)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int dfs(const int &vf,const vector<vector<int> > &graph,int &l)
{
stack<int> s;
vector<bool> visited;
visited.resize(graph.size(),false);
s.push(vf);
visited[vf]=true;
int k=0,i,aux,pm=vf;
bool found;
while(!s.empty())
{
aux=s.top();
if(k>l)
{
pm=aux;
l=k;
}
found=false;
//cout<<"\nk == "<<k<<"; diam == "<<l<<"\nMa aflu pe nodul "<<aux+1<<'\n';
for(i=0;i<graph[aux].size() && !found;i++)
{
if(!visited[graph[aux][i]])
found=true;
}
if(found)
{
//cout<<"Am gasit "<<graph[aux][i-1]+1<<'\n';
s.push(graph[aux][i-1]);
visited[graph[aux][i-1]]=true;
k++;
}
else
{
s.pop();
k--;
}
}
return pm;
}
int main()
{
int n,i,x,y,pmin;
ifstream fin("darb.in");
ofstream fout("darb.out");
fin>>n;
vector<vector<int> > graph;
vector<int> grade;
graph.resize(n);
grade.resize(n,0);
for(i=0;i<n-1;i++)
{
fin>>x>>y;
x--; y--;
graph[x].push_back(y); graph[y].push_back(x);
grade[x]++; grade[y]++;
if(grade[x]<grade[pmin]) pmin=x;
if(grade[y]<grade[pmin]) pmin=y;
}
int cent1=-1,cent2=-1,vf1=0,vf2=0,vaux1=0,vaux2=0,diam=0,diaux=0;
vf1=pmin;
vf2=dfs(vf1,graph,diam);
vaux1=vf2;
vaux2=dfs(vaux1,graph,diaux);
if(diaux>diam)
{
diam=diaux;
vf1=vaux1;
vf2=vaux2;
}
//cout<<vf1+1<<' '<<vf2+1;
fout<<diam+1;
return 0;
}