Cod sursa(job #2618530)

Utilizator RobertLearnsCDragomir Robert. RobertLearnsC Data 25 mai 2020 13:02:58
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> graph[200005];
int n, visited[200005], dist[200005], maxi;

void dfs(int currNode, int &maxi) {
    visited[currNode] = 1;
    for(int i = 0; i < graph[currNode].size(); ++i) {
        int neighbor_index = graph[currNode][i];
        if(!visited[neighbor_index]) {
            dist[neighbor_index] = dist[currNode] + 1;
            dfs(neighbor_index, maxi);
        }
    }
}

void getMaxDist(int &maxi, int &bound, int format) {
    for(int i = 0; i < n; ++i) {
        if(dist[i] > maxi) {
            maxi = dist[i];
            bound = i;
        }
    }
    if(format == 2) {
        printf("%d", maxi);
    }
}

void prepDFS(int source) {
    dist[source] = 1;
    dfs(source, maxi);
}

int main() {
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 0; i < n - 1; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x - 1].push_back(y - 1);
        graph[y - 1].push_back(x - 1);
    }

    int bound = 0;
    prepDFS(1);
    getMaxDist(maxi, bound, 1);

    memset(visited, 0, sizeof(visited));
    memset(dist, 0, sizeof(dist));

    prepDFS(bound);
    getMaxDist(maxi, bound, 2);

    return 0;
}