Cod sursa(job #1320692)

Utilizator andreey_047Andrei Maxim andreey_047 Data 18 ianuarie 2015 12:53:58
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
vector<int>G[nmax];
int v[nmax],ok,lg,n,d[nmax],lgmax,s;
void DFS(int x,int lg){
 v[x]=1;
 for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
  if(!v[*it])DFS(*it,lg+1);
   if(lg>lgmax) {lgmax=lg;s=x;}
}
void Attack(int si,int sf){
 int Q[nmax],k,i,j;
  k=1;
  for(i=1;i<=n;i++)d[i]=-1;
  d[si]=0;
  Q[1]=si;
  for(i=1;i<=k;i++)
   for(j=0;j<G[Q[i]].size();j++)
    if(d[G[Q[i]][j]]==-1||d[G[Q[i]][j]] > 1+d[Q[i]]){
     d[G[Q[i]][j]]=d[Q[i]]+1;
     Q[++k]=G[Q[i]][j];
    }
}
int main(){
    int i,x,y,si,sf;
    ifstream fin("darb.in");
    fin>>n;
    for(i=1;i<n;i++){
      fin>>x>>y;
      G[x].push_back(y);
      G[y].push_back(x);
    }
  fin.close();
  DFS(1,1);
  si=s;
  ok=0;
  for(i=1;i<=n;i++)
   v[i]=0;
   lgmax=0;
  DFS(s,1);
  sf=s;
  Attack(si,sf);
  ofstream fout("darb.out");
  fout<<d[sf]+1<<'\n';
  fout.close();
    return 0;
}