Cod sursa(job #1639583)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 8 martie 2016 12:55:24
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define MAXN 100050

vector <int> edge[MAXN];
vector <vector <int> > Global;
int N, last;

void BFS(int node)
{
    vector <int> used, dist;
    queue <int> NodeQ;

    used.resize(N+1);
    dist.resize(N+1);

    used[node] = 1;
	dist[node] = 1;

	NodeQ.push(node);

	while (!NodeQ.empty())
	{
        node = NodeQ.front();
        for (int i = 0; i < (int) edge[node].size(); ++i)
			if (!used[edge[node][i]])
			{
				dist[edge[node][i]] = dist[node] + 1;
				NodeQ.push(edge[node][i]);
				used[edge[node][i]] = 1;
				last = edge[node][i];
			}
		NodeQ.pop();
	}

	Global.push_back(dist);

}

int main()
{
    fin >>N;

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

	BFS(1);
	BFS(last);

	fout <<Global[1][last] <<'\n';
	fout.close();

    return 0;
}