Cod sursa(job #1709724)

Utilizator CornelPanicUPB CornelPanic CornelPanic Data 28 mai 2016 13:37:45
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream in("revolta.in");
ofstream out("revolta.out");

const int MAXN = 100010;

int N;
vector <int> Graf[MAXN];
bool Viz[MAXN];

int maxDist, departeNod, numberOf;
void getDeparte(int nod, int level) {
    Viz[nod] = 1;

    if (level > maxDist) {
        maxDist = level;
        departeNod = nod;
        numberOf = 1;
    } else if (level == maxDist) {
        numberOf++;
    }

    for (auto it : Graf[nod]) {
        if (!Viz[it]) {
            getDeparte(it, level + 1);
        }
    }
}

int main() {
    int i, a, b, T;
    in >> T;
    while(T--) {
        maxDist = 0;
        memset(Viz, 0, sizeof(Viz));
        in >> N;
        for (i = 0; i < N; i++) {
            Graf[i].clear();
        }
        for (i = 1; i < N; i++) {
            in >> a >> b;
            Graf[a].push_back(b);
            Graf[b].push_back(a);
        }

        getDeparte(0, 0);
        maxDist = 0;
        numberOf = 1;
        memset(Viz, 0, sizeof(Viz));
        getDeparte(departeNod, 0);

        if (numberOf == 1) {
            if (maxDist == 1) {
                maxDist = 2;
            }
            out << maxDist - 1 << "\n";
        } else {
            out << maxDist << "\n";
        }
    }

    return 0;
}