Cod sursa(job #1316798)

Utilizator andreey_047Andrei Maxim andreey_047 Data 14 ianuarie 2015 09:46:08
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <Vector>
#define nmax 100005
using namespace std;
vector<int>G[nmax];
int v[nmax],ok,s,n,d[nmax];
void DFS(int x){
 v[x]=1;
 for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
  if(!v[*it])DFS(*it);
   if(!ok){ok=1;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);
  si=s;
  ok=0;
  for(i=1;i<=n;i++)
   v[i]=0;
  DFS(s);
  sf=s;
  Attack(si,sf);
  ofstream fout("darb.out");
  fout<<d[sf]+1<<'\n';
  fout.close();
    return 0;
}