[TIOJ] 1152. 1.銀河帝國旅行社

題目連結:http://tioj.infor.org/problems/1152

---

裸的樹直徑題，那樹直徑要怎麼做呢?有個greedy的做法:先隨便從一個點DFS下去，走到最遠的地方後，再從那個點DFS下去走到離他最遠的點，則這兩個點中間的路徑就會是直徑。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const int N = 10000 + 5;

vector<int> G[N];
void dfs(int,int,int,PII&);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++){
		int x;
		while(cin>>x and x!=-1){
			G[i].PB(x);
			G[x].PB(i);
		}
	}
	PII ans = {0, -1};
	dfs(0, 0, 0, ans);
	ans.SS = -1;
	dfs(ans.FF, ans.FF, 0, ans);
	cout<<ans.SS<<'\n';
	return 0;
}

void dfs(int w, int f, int sum, PII& ret){
	if(sum > ret.SS) ret = {w, sum};
	for(auto i: G[w]){
		if(i==f) continue;
		dfs(i, w, sum+1, ret);
	}
}