1021 Deepest Root (25分)

1021 Deepest Root (25分)
先用dfs数出图的连通分量数count,如果连通分量数count > 1直接输出结果;
如果count == 1,说明该图连通,又因为图中只有n - 1条边,该图必然为无环图,对每个根节点进行dfs,找出根的最大深度。

#include<cstdio>
#include<unordered_set>
#include<vector>
#include<set>
using namespace std;
int n;
unordered_set<int> map[10001];
bool visited[10001];
void dfs(int cur) {
	visited[cur] = true;
	for (int e : map[cur]) {
		if (!visited[e])
			dfs(e);
	}
}
int countComponent() {
	int count = 0;
	for (int i = 1;i <= n;i++) {
		if (!visited[i]) {
			dfs(i);
			count++;
		}
	}
	return count;
}
int maxDepth = 0, source;
set<int> res;
void findDeepest(int cur, int depth) {
	visited[cur] = true;
	bool hasMoreVertex = false;
	for (int e : map[cur]) {
		if (!visited[e]) {
			hasMoreVertex = true;
			findDeepest(e, depth + 1);
		}
	}
	if (!hasMoreVertex) {
		if (depth > maxDepth) {
			res.clear();
			maxDepth = depth;
			res.insert(cur);
			res.insert(source);
		}
		else if (depth == maxDepth) {
			res.insert(cur);
			res.insert(source);
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0;i < n - 1;i++) {
		int v1, v2;
		scanf("%d %d", &v1, &v2);
		map[v1].insert(v2);
		map[v2].insert(v1);
	}
	int count = countComponent();
	if (count == 1) {
		for (int i = 1;i <= n;i++) {
			if (map[i].size() > 1 || res.find(i) != res.end())
				continue;
			fill(visited, visited + 10001, false);
			source = i;
			findDeepest(i, 0);
		}
		for (int e : res)
			printf("%d\n", e);
	}
	else printf("Error: %d components\n", count);
}
上一篇:Java学习--String、StringBuffer与StringBuilder


下一篇:谷歌坐标转百度坐标