Cod sursa(job #2271747)

Utilizator HerddexJinga Tudor Herddex Data 29 octombrie 2018 10:26:29
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

struct Node{
    int node;
    Node *next;
}*G[100001];

int N;

int finalDistance;

int furthestNodeFrom(int v)
{
    int Q[100000];
    bool isVisited[100001];
    for(int i=1; i<=N; i++)
        isVisited[i] = false;
    isVisited[v] = true;
    int dist[100001];
    dist[v] = 0;
    int first = 0;
    int last = 0;
    Q[first] = v;

    int maxDistance = 0;
    int furthestNode;
    while(first<=last)
    {
        for(Node *p = G[Q[first]]; p!=0; p = p->next)
            if(!isVisited[p->node])
            {
                last++;
                Q[last] = p->node;
                isVisited[p->node] = true;
                dist[p->node] = dist[Q[first]] + 1;
                if(dist[p->node] > maxDistance)
                {
                    maxDistance = dist[p->node];
                    furthestNode = p->node;
                }
            }
        first++;
    }
    finalDistance = maxDistance;
    return furthestNode;
}

int main()
{
    fin >> N;

    for(int k=1; k<=N-1; k++)
    {
        int v, w;
        fin >> v >> w;
        Node *p = new Node;
        p->node = w;
        p->next = G[v];
        G[v] = p;
        p = new Node;
        p->node = v;
        p->next = G[w];
        G[w] = p;
    }

    int chainStart = furthestNodeFrom(1);
    int chainEnd = furthestNodeFrom(chainStart);
    fout << finalDistance + 1;

    fin.close();
    fout.close();
    return 0;
}