Cod sursa(job #1752487)

Utilizator TrascaAndreiTrasca Andrei TrascaAndrei Data 4 septembrie 2016 01:37:27
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define N 1000001

using namespace std;

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

vector<int> nod[N];
queue<int> c;

int n,contor[N],last,diam;
bool viz[N];

void bfs(int x){
    memset(contor,0,N);
    memset(viz,0,N);
    c.push(x);
    contor[x]=1;
    viz[x]=1;

    int i,a;
    while(!c.empty()){
        a=c.front();
        for(i=0;i<nod[a].size();i++){
            if(viz[nod[a][i]]==0){
                c.push(nod[a][i]);
                contor[nod[a][i]]=contor[a]+1;
                viz[nod[a][i]]=1;
                diam=contor[a]+1;
                last=nod[a][i];
            }
        }
        c.pop();
    }
}

void cit(){
    int i,a,b;
    fin>>n;
    for(i=0;i<n-1;i++){
        fin>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
}

int main()
{
    cit();
    bfs(1);
    bfs(last);
    fout<<diam;
    return 0;
}