Cod sursa(job #2632560)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 3 iulie 2020 19:57:14
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

const char* inputFile = "darb.in";
const char* outputFile = "darb.out";

unsigned N, cont, maxx, leaf;

#define NMAX 500000
std::vector<unsigned> adj[NMAX];
std::vector<bool> viz;
#undef NMAX

void dfs(unsigned src)
{
    for(unsigned i = 0; i < adj[src].size(); ++i)
    {
        unsigned curr = adj[src][i];
        if(!viz[curr])
        {
            ++cont;
            if(cont > maxx)
            {
                maxx = cont;
                leaf = curr;
            }
            viz[curr] = true;
            dfs(curr);
        }
    }
    --cont;
}

int main(void)
{
    FILE* pf = fopen(inputFile, "r");
    fscanf(pf, "%u", &N);
    #define pb push_back
    for(unsigned i = 1; i < N; ++i)
    {
        unsigned u, v;
        fscanf(pf, "%u%u", &u, &v);
        adj[u].pb(v), adj[v].pb(u);
    }
    #undef pb
    fclose(pf);
    viz.resize(N + 1);
    viz[1] = true;
    cont = maxx = leaf = 1;
    dfs(1);
    viz.assign(N + 1, false);
    viz[leaf] = true;
    cont = maxx = 1;
    dfs(leaf);
    pf = fopen(outputFile, "w");
    fprintf(pf, "%u", maxx);
    fclose(pf);
    return 0;
}