Cod sursa(job #2696511)

Utilizator Cibotaru.MateiMatei-Stefan Cibotaru Cibotaru.Matei Data 16 ianuarie 2021 04:17:42
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
using namespace std;

int main() {
    ifstream f("darb.in");
    int n;
    f >> n;
    vector<list<int>> graph(n + 1);
    
    for (int i = 1; i < n; i++) {
        int x, y;
        f >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    ofstream g("darb.out");
    vector<bool> visited(n + 1, false);
    stack<int> stack, newstack;
    stack.push(1);
    int maxim = 0;

    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();
        visited[node] = true;
        maxim = node;
        for (auto& i : graph[node]) {
            if (!visited[i]) {
                newstack.push(i);
            }
        }

        if (stack.empty()) {
            stack = newstack;
            while (!newstack.empty()) {
                newstack.pop();
            }
        }
    }

    stack.push(maxim);
    int level = 0;

    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }

    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();
        visited[node] = true;
        for (auto& i : graph[node]) {
            if (!visited[i]) {
                newstack.push(i);
            }
        }

        if (stack.empty()) {
            level++;
            stack = newstack;
            while (!newstack.empty()) {
                newstack.pop();
            }
        }
    }

    g << level;
}