Cod sursa(job #1901538)

Utilizator gabib97Gabriel Boroghina gabib97 Data 4 martie 2017 01:19:21
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

#define N 100005
using namespace std;
int n, i, t, h[N], st, dr, l, g[N], T[N];
bool o[N];
vector<int> G[N];
vector<int> diam;

void DFS_diam(int s) {
    int m1, m2, a, b;
    m1 = m2 = 0;
    h[s] = 1;
    g[s] = s;
    for (auto x:G[s])
        if (!h[x]) {
            DFS_diam(x);
            if (h[x] + 1 > h[s])
                h[s] = h[x] + 1, g[s] = g[x]; //max depth
            if (h[x] > m1) {
                m2 = m1;
                m1 = h[x];
                b = a;
                a = g[x];
            } else if (h[x] > m2) m2 = h[x], b = g[x];
        }
    if (m2) {
        if (l < m1 + m2 + 1) {
            l = m1 + m2 + 1;
            st = a;
            dr = b;
        }
    } else {
        if (l < m1 + 1) {
            l = m1 + 1;
            st = s;
            dr = a;
        }
    }
}

void DFS(int s) {
    o[s] = 1;
    for (auto x:G[s])
        if (!o[x]) {
            T[x] = s;
            DFS(x);
        }
}

int main() {
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int x, y;
    scanf("%d", &t);
    while (t--) {
        scanf("%i", &n);
        for (i = 1; i <= n; i++) G[i].clear();
        memset(o, 0, (n + 1) * sizeof(bool));
        for (i = 1; i < n; i++) {
            scanf("%i%i", &x, &y);
            G[x + 1].push_back(y + 1);
            G[y + 1].push_back(x + 1);
        }

        DFS_diam(2);
        l = 0;
        DFS(st); //capetele diametrului
        for (i = dr; i != st; i = T[i])
            diam.push_back(i);
        diam.push_back(st);
        printf("%i", diam.size());
        //DFS(dr);
    }

    return 0;
}