Cod sursa(job #1410313)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 30 martie 2015 23:33:43
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define nmax 100005

using namespace std;

FILE *fi, *fo;

int n, frunza, nivFrz;
vector <int> G[nmax];
bool viz[nmax];

void dfs(int nod, int niv)
{
    viz[nod] = true;
    
    for (int i = 0; i < G[nod].size(); i++)
        if (!viz[G[nod][i]])
            dfs(G[nod][i], niv + 1);
    
    if (nivFrz < niv)
    {
        nivFrz = niv;
        frunza = nod;
    }
}

int main()
{
    
    fi = fopen("darb.in", "r");
    fo = fopen("darb.out", "w");
    
    fscanf(fi, "%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        fscanf(fi, "%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    
    dfs(1, 1);
    
    memset(viz, false, sizeof(viz));
    nivFrz = 0;
    
    dfs(frunza, 1);
    
    fprintf(fo, "%d\n", frunza);
    
    fclose(fi);
    fclose(fo);
    
    return 0;
}