Cod sursa(job #1668417)

Utilizator IoanaPPascu Ioana IoanaP Data 29 martie 2016 19:43:34
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>

using namespace std;

long n, i, x, y, s;
vector <vector <long> > graph;
vector <long> viz;
ifstream f ("darb.in");
ofstream g ("darb.out");

void DFS (long vertex){
    long i, maxi = 0, mid1 = -1, mid2 = -1, niv = 1, aux, elem;
    bool found;

    if (vertex < 0 || vertex > n-1) return;
    vector <long> s;
    for (i = 0; i < n; i++) viz[i] = -1;
    s.push_back (vertex);
    viz[vertex] = 1;
    while (!s.empty()) {
        elem = s[s.size() - 1];
        found = false;
        for (i = 0; i < graph[elem].size() && !found; i++)
           if (viz[graph[elem][i]] == -1) {
                found = true;
                aux = i;
           }
        if (found) {
            i = aux;
            s.push_back (graph[elem][i]);
            viz [graph[elem][i]] = 1;
            niv++;
            if (niv > maxi) {
                maxi = niv;
               /* if (s.size() % 2 == 0) {
                    mid1 = s[s.size() / 2];
                    mid2 = s[s.size() / 2 - 1];
                }
                 else {
                    mid1 = s[s.size() / 2];
                    mid2 = -1;
                 }*/
            }
        }
         else {
            s.pop_back();
            niv--;
         }
    }
    g << maxi << endl;
    /*if (mid2 != -1) cout << mid1 + 1 << " " << mid2 + 1;
     else cout << mid1 + 1;*/
}

long BFS (long vertex){
    long i;
    if (vertex < 0 || vertex > n-1) return -1; //daca nodul are valoare invalida iesim
    queue <long> q;
    long elem;
    q.push (vertex); //punem nodul de la care pornim in coada
    viz[vertex] = 0;
    while (!q.empty()) {
        elem = q.front();
        for (i = 0; i < graph[elem].size(); i++)
           if (viz[graph[elem][i]] == -1) {
                q.push (graph[elem][i]);
                viz [graph[elem][i]] = viz[elem] + 1;
           }
        q.pop(); //eliminam nodul pentru care am analizat deja vecinii
        }
    long maxi = 0;
    for (i = 1; i < n; i++)  if (viz[i] > viz[maxi]) maxi = i;
    return maxi + 1; //intoarcem nodul cel mai indepartat
}

int main()
{
    f >> n;
    graph.resize(n);
    viz.resize(n, -1);
    for (i = 0; i < n - 1; i++)
    {
        f >> x >> y;
        x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    long cap = BFS(0);
    //cout << cap << endl;

    DFS(cap - 1);

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