Cod sursa(job #1492266)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 27 septembrie 2015 14:56:38
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

int maxDepth;
int maxDepthNode;

void dfs(int node, vector<vector<int> > & G, vector<int> & color, int depth) {
    if (depth > maxDepth) {
        maxDepth = depth;
        maxDepthNode = node;
    }

    color[node] = 1;
    for (int neighIndex = 0; neighIndex < G[node].size(); ++neighIndex) {
        int neigh = G[node][neighIndex];
        if (color[neigh] == 0)
            dfs(neigh, G, color, depth + 1);
    }
    color[node] = 2;
}

int main()
{
    int N, x, y;
    fin >> N;

    vector<vector<int> > G(N + 1, vector<int>());
    vector<int> color(N + 1, 0);

    for (int i = 1; i < N; ++i) {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(1, G, color, 0);
    for (int i = 0; i <= N; ++i) color[i] = 0;
    maxDepth = 0;
    int startNode = maxDepthNode;
    dfs(startNode, G, color, 0);

    fout << maxDepth + 1 << '\n';

    return 0;
}