Cod sursa(job #1488809)

Utilizator Liviu98Dinca Liviu Liviu98 Data 19 septembrie 2015 21:34:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#define NMax 100001
using namespace std;
vector<int> Graf[NMax];
int dist[NMax],N,ultim,x,y,Max;
bool mark[NMax];

void Citire()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }
}

void DFS1(int nod)
{
    for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
    {
        if(mark[*it]==false)
        {
            mark[*it]=true;
            dist[*it]=dist[nod]+1;
            if(Max<dist[*it])
            {
                Max=dist[*it];
                ultim=*it;
            }
            DFS1(*it);
        }
    }
}

void DFS2(int nod)
{
    for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
    {
        if(mark[*it]==true)
        {
            mark[*it]=false;
            dist[*it]=dist[nod]+1;
            if(Max<dist[*it])
            {
                Max=dist[*it];
                ultim=*it;
            }
            DFS2(*it);
        }
    }
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    Citire();

    dist[x]=1;
    DFS1(x);

    dist[ultim]=1;
    DFS2(ultim);

    printf("%d",Max);
}