Cod sursa(job #1369445)

Utilizator Toast97Calin Farcas Toast97 Data 3 martie 2015 08:21:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>

using namespace std;

ifstream f ("darb.in");
ofstream g ("darb.out");

struct nod
{
    int info;
    nod *adr;
} *v[100005];

void adaugare (int tata, int fiu)
{
    nod *c;
    c = new nod;
    c -> info = fiu;
    c -> adr = v[tata];
    v[tata] = c;
}

int n, primul, viz[100005], diametru = 0;

void citire ()
{
    f >> n;

    int a, b;

    for (int i = 1; i < n; i ++)
    {
        f >> a >> b;
        adaugare (a, b);
        adaugare (b, a);
    }
}

void dfs (int node, int cost)
{
    viz[node] = 1;
    if (cost > diametru)
        {
            diametru = cost;
            primul = node;
        }

    nod *c;
    c = v[node];

    while (c)
    {
        if (!viz[c -> info])
            dfs (c -> info, cost + 1);

        c = c -> adr;
    }
}

int main()
{
    citire ();

    dfs (1, 1);
    diametru = 0;

    for (int i = 1; i < n; i ++)
        viz[i] = 0;

    dfs (primul, 1);

    g << diametru;

    f.close ();
    g.close ();
    return 0;

}