Cod sursa(job #2440500)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 18 iulie 2019 16:15:08
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <string.h>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
stack<int> s;
vector<int> v[100500];
bool vis[100500];
int n,tp,last,maxx;

void dfs(int t, bool first)
{
  s.push(t);
  memset(vis,0,sizeof(vis));
  vis[t]=true;
  while(!s.empty())
  {
    tp=s.top();
    int i=0;
    for(;i<v[tp].size();i++)
    {
      int elem = v[tp][i];
      if(!vis[elem])
      {
        vis[elem]=true;
        s.push(elem);
        if(s.size()>maxx)
        {
          if(first) last=s.top();
          maxx=s.size();
        }
        break;
      }
    }
    if(i==v[tp].size())
      s.pop();
  }
}

int main()
{
  fin>>n;
  for(int i=0;i<n-1;i++)
  {
    int j,k;
    fin>>j>>k;
    v[j].push_back(k);
    v[k].push_back(j);
  }
  dfs(1,true);
  dfs(last,false);
  fout<<maxx<<"\n";
}