나무의 지름

나무 에서 가장 먼 두 정점 의 거 리 를 구 하 는 것 이 바로 나무의 지름 을 구 하 는 것 이다.방법 은 두 번 의 BFS 나 DFS 이다.r 는 나무 T 의 뿌리 이 고 u 는 r 에서 가장 먼 결점 이 며 v 는 u 에서 가장 먼 결점 이다.나무의 지름 은 d(u,v)이다.반증 법 으로 증명 할 수 있다. （그림 의 지름 은 Floyd 로 만 들 수 있다.DFS 를 끝내 고 노드 번호 로 돌아 가면 됩 니 다.두 번 호출 완료,anspath 에 기 록 된 게 지름 이에 요.POJ 연습 문제 가 있 습 니 다.시간 이 있 으 면 연습 할 수 있 습 니 다http://wenku.baidu.com/view/00d9168984868762caaed5a4.html
DFS 를 여러 번 호출 해 야 하 는 상황 에서 여러 번 memset visited[N]는 많은 시간 을 소모 합 니 다(N 이 크기 때문에).변 수 를 추가 할 수 있 습 니 다 visitedid,매번 DFS,visitedid++,그리고 visited[N]==visited 판단id 면 돼.

#include <vector>;

using namespace std;



const static int N = 200003;

bool visited[N];

vector<int> curr_path;

vector<int> ans_path;

void dfs_helper(vector<vector<int>> &tree, int root, vector<int> &curr, vector<int> &ans) {

	if (visited[root]) {

		return;

	}

	visited[root] = true;

	curr.push_back(root);

	if (curr.size() > ans.size()) {

		ans = curr; // vector copy, but most d times, d is the length of the diameter

	}

	int m = tree[root].size();

	for (int i = 0; i < m; i++) {

		dfs_helper(tree, tree[root][i], curr, ans);

	}

	curr.pop_back();

}



int dfs(vector<vector<int>> &tree, int root) {

	curr_path.clear();

	ans_path.clear();

	memset(visited, false, sizeof(visited));

	dfs_helper(tree, root, curr_path, ans_path);

	return ans_path.back();

}



int main()

{

	// int root = dfs(tree, 0);

	// dfs(tree, root);

	// then the ans_path is the shortest path in the tree

}