Cod sursa(job #1876491)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 12 februarie 2017 13:42:06
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMax 100005

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

int N,K;
vector<int> Graf[NMax];
int viz[NMax];
int ultimulNod,nrMax;
int nrDFS;

void Read()
{
    fin>>N>>K;
    for(int i=1;i<N;i++)
    {
        int x,y;
        fin>>x>>y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }
}

void DFS(int nod,int nr)
{
    viz[nod]=nrDFS;
    if(nr>nrMax)
        nrMax=nr, ultimulNod=nod;
    for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
        if(viz[*it]!=nrDFS)
            DFS(*it,nr+1);
}

int main()
{
    Read();
    nrDFS=1; viz[1]=nrDFS; DFS(1,1);
    nrDFS=2; nrMax=0; DFS(ultimulNod,1);
    fout<<nrMax;

    return 0;
}