Cod sursa(job #2696510)

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

int level = 0, maxlev = 0, maxim = 0;

int dfs(vector<list<int>>& graph, vector<bool>& visited, int start) {
    visited[start] = true;
    level++;
    if (level > maxlev) {
        maxlev = level;
        maxim = start;
    }
    for (auto& i : graph[start]) {
        if (!visited[i]) {
            maxim = dfs(graph, visited, i);
        }
    }
    level--;
    return maxim;
}

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);

    int newstart = dfs(graph, visited, 1);
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    level = maxlev = maxim = 0;

    dfs(graph, visited, newstart);
    g << maxlev;
}