Cod sursa(job #1430981)

Utilizator GilgodRobert B Gilgod Data 8 mai 2015 22:35:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <list>
#include <bitset>

#define INF 0x3f3f3f3f
#define NMAX 100001

const char IN[] = "darb.in", OUT[] = "darb.out";

using namespace std;

list<int> G[NMAX];
int N;

inline void readData() {
	freopen(IN, "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		int s, d;
		scanf("%d %d", &s, &d);
		G[s].push_back(d);
		G[d].push_back(s);
	}
	fclose(stdin);
}

int maxDisc = -INF;
int maxNode;

bitset<NMAX> visited;

void dfs(int node, int dist) {
	if (maxDisc < dist) {
		maxDisc = dist;
		maxNode = node;
	}
	for (auto& n : G[node]) {
		if (!visited[n]) {
			visited[n].flip();
			dfs(n, dist+1);
		}
	}
}

int main() {
	readData();
	dfs(1, 0);
	visited.reset();
	maxDisc = -INF;
	dfs(maxNode, 0);
	freopen(OUT, "w", stdout);
	printf("%d\n", maxDisc + 1);
	fclose(stdout);
	return 0;
}