1021 Deepest Root (25 分)
1.首先记得h要清空为-1
2.然后边的数量是n-1,不是n
3.因为是无向图,双向,所以说边的数量要乘2。
4.搜索联通块既可以用并查集,也可以用dfs搜索。
5.由于数据范围是10^4,时间是2s,所以暴搜n^2也可以过。
6.由于是无向图,所以在dfs遍历这棵树的时候,不能遍历回父结点。如果使用的是用st数组来记录点是否遍历过,那么每一个结点都需要memset,这样做很花费时间。所以说,记录父结点,如果遍历至该结点到父结点的边的话,就continue。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 10010, M = 20010;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
vector<int> v;
int cur_max;
void add(int a,int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs_cnt(int x)
{
if(st[x]) return;
st[x] = true;
for(int i=h[x];i!=-1;i=ne[i]){
dfs_cnt(e[i]);
}
}
int dfs(int x,int father)
{
if(h[x] == -1) return 1;
int depth = 0;
for(int i=h[x];i!=-1;i=ne[i]){
int j = e[i];
if(j == father) continue;
depth = max(depth,dfs(j,x));
}
return depth+1;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<=n-1;i++){
int a, b;
cin>>a>>b;
add(a,b),add(b,a);
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(!st[i]) cnt++,dfs_cnt(i);
}
if(cnt>1){
printf("Error: %d components\n",cnt);
return 0;
}
for(int i=1;i<=n;i++){
int depth = dfs(i,-1);
if(depth > cur_max){
cur_max = max(cur_max,depth);
v.clear();
v.push_back(i);
}else if(depth == cur_max){
v.push_back(i);
}
}
for(int i=0;i<v.size();i++){
cout<<v[i]<<endl;
}
return 0;
}
自己写的用memset会TLE。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 20010;
int n;
int h[N], e[N], ne[N], idx;
bool st[N];
int p[N];
vector<int> v;
int cur_max;
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void add(int a,int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int x)
{
st[x] = true;
if(h[x] == -1) return 1;
int depth = 0;
for(int i=h[x];i!=-1;i=ne[i]){
int j = e[i];
if(!st[j]) depth = max(depth,dfs(j));
}
return depth+1;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
int cnt = n;
for(int i=1;i<=n;i++) p[i] = i;
for(int i=1;i<=n-1;i++){
int a, b;
cin>>a>>b;
if(find(a) != find(b)){
cnt--;
p[find(a)] = find(b);
}
add(a,b),add(b,a);
}
if(cnt > 1){
printf("Error: %d components\n",cnt);
return 0;
}
for(int i=1;i<=n;i++){
memset(st,0,sizeof st);
int depth = dfs(i);
if(depth > cur_max){
cur_max = max(cur_max,depth);
v.clear();
v.push_back(i);
}else if(depth == cur_max){
v.push_back(i);
}
}
for(int i=0;i<v.size();i++){
cout<<v[i]<<endl;
}
return 0;
}