[PAT解题报告] Deepest Root
给定一棵树 （无向无环图）——先判断给定的到底是不是树，如果是树，以那些节点为根能得到的尽可能高的树。
分析： 判断是否是树比较简单，可以用dfs,
bfs求连通分量，如果是1就是树，当然我采取的是并查集，类似kruskal算法加边，顺便统计连通分量的个数。然后有两种办法处理。一种是暴力——比较好理解，以每个节点为根dfs一次求出高度。这种算法的时间复杂度是O(n2)，好在n不大10000，这种暴力可以通过。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
using namespace std;
int f[100005];
vector<int> con[100005];
vector<int> v;
int c,maxd;
int getf(int x) {
return f[x] = ((x == f[x])?x:getf(f[x]));
}
void make(int x,int y) {
x = getf(x);
y = getf(y);
if (x != y) {
f[x] = y;
--c;
}
}
int dfs(int x,int father) {
int d = 0;
for (int i = 0; i < con[x].size(); ++i) {
if (con[x][i] != father) {
d = max(d, dfs(con[x][i], x));
}
}
return d + 1;
}
int main() {
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
f[i] = i;
}
c = n;
for (int i = n - 1; i; --i) {
int x,y;
scanf("%d%d",&x,&y);
make(--x, --y);
con[x].push_back(y);
con[y].push_back(x);
}
if (c > 1) {
printf("Error: %d components\n",c);
}
else {
int depth = 0;
for (int i = 0; i < n; ++i) {
depth = max(depth, dfs(i, -1));
}
for (int i = 0; i < n; ++i) {
if (dfs(i, - 1) == depth) {
printf("%d\n", i + 1) ;
}
}
}
return 0;
}
另外一种算法比较巧妙，先从任意一个点dfs，可以得到一些点距离这个点最远，再从第一次dfs保存这些点中的任意一个dfs，得到距离它最远的点，两次得到的全部点就是答案。这种算法的时间复杂度直接降为O(n)——关键要理解一个结论到达树中最远的两个点可以通过两次dfs得到。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
using namespace std;
int f[100005];
vector<int> con[100005];
vector<int> v;
int c,maxd;
int getf(int x) {
return f[x] = ((x == f[x])?x:getf(f[x]));
}
void make(int x,int y) {
x = getf(x);
y = getf(y);
if (x != y) {
f[x] = y;
--c;
}
}
void dfs(int x,int father,int dep) {
if (dep > maxd) {
maxd = dep;
v.resize(1);
v[0] = x;
}
else if (dep == maxd) {
v.push_back(x);
}
for (int i = 0; i < con[x].size(); ++i) {
if (con[x][i] != father) {
dfs(con[x][i], x , dep + 1);
}
}
}
int main() {
scanf("%d",&c);
for (int i = 0; i < c; ++i) {
f[i] = i;
}
for (int i = c - 1; i; --i) {
int x,y;
scanf("%d%d",&x,&y);
make(--x, --y);
con[x].push_back(y);
con[y].push_back(x);
}
if (c > 1) {
printf("Error: %d components\n",c);
}
else {
maxd = -1;
dfs(0, -1, 0);
set<int> all;
for (int i = 0; i < v.size(); ++i) {
all.insert(v[i]);
}
maxd = -1;
dfs(v[0], -1, 0);
for (int i = 0; i < v.size(); ++i) {
all.insert(v[i]);
}
for (set<int>::iterator t = all.begin(); t != all.end(); ++t) {
printf("%d\n",(*t) + 1);
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1021
查看11道真题和解析