Cod sursa(job #1932757)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 20 martie 2017 08:32:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define x first
#define y second
#define mod 1000000007
 
using namespace std;

int n, m, mx, x, y;
int pas[100100];
vector < int > V[100100];
bitset < 100100 > viz;


void dfs(int x)
{
	viz[x] = 1;
	for (auto it : V[x])
		if (!viz[it]) pas[it] = pas[x] + 1, mx = max(pas[it], mx), dfs(it);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream cin("darb.in");
    ofstream cout("darb.out");
    cin >> n;
    for (int i = 1; i < n; i++)
		cin >> x >> y,
		V[x].push_back(y),
		V[y].push_back(x);
	pas[1] = 0;
	int node;
	dfs(1);
	for (int i = 1; i <= n; i++)
		if (pas[i] == mx){node = i; break;}
	mx = 1;
	memset(pas, 0, sizeof(pas));
	viz.reset();
	pas[node] = 1;
	dfs(node);
	cout << mx;
    return 0;
}