Cod sursa(job #1094531)

Utilizator VincentVegaVincent Vega VincentVega Data 29 ianuarie 2014 15:32:26
Problema Elementul majoritar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

int N;
vector<int> G[100005];
queue<int> Q;
int dist[100005];

inline int BFS(const int &start)
{
	int last = 0;
	
	for (int i = 1; i <= N; ++i)
		dist[i] = false;
	while (Q.size())
		Q.pop();
	
	for (Q.push(start), dist[start] = 1; Q.size(); Q.pop())
	{
		const int ret = Q.front();
	
		for (vector<int>::iterator i = G[ret].begin(); i != G[ret].end(); ++i)
		{
			if (!dist[*i])
			{
				dist[*i] = dist[ret] + 1;
				Q.push(*i);
				last = *i;
			}
		}
	}
	
	return last;
}

int main()
{
	fin >> N;
	for (int i = 1; i <= N; ++i)
	{
		int X, Y;
		fin >> X >> Y;
		G[X].push_back(Y);
		G[Y].push_back(X);
	}
	
	fout << dist[BFS(BFS(1))] << '\n';
}