无环图的最大半径

---

image.png

PS: 已知该图为一个最小生成树（点数=边数+1）：

---

1. 暴力解法：逐个带入DFS

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
#define N 1000
int dfsmax=0,points;
bool isoccupy[N]={false};
void DFSv(vector<vector<int>>v,int start,int record){
  int i,j;
  isoccupy[start]=true;
  bool signal=false;
  for(i=0;i<v[start].size();i++){
    if(!isoccupy[v[start][i]])
    {
      signal=true;
      DFSv(v,v[start][i],record+1);
    }
  }
  if(signal==false){
    dfsmax=max(dfsmax,record);
  }
  isoccupy[start]=false;
}
void DFS(vector<vector<int>>v){
  int i,j;
  int record=0;
  for(i=1;i<=points;i++){
    DFSv(v,i,record);
    record=0;
  }
}
int main(){
  vector<vector<int>>v;
  int edges,i,j,circle;
  scanf("%d\n",&circle);
  for(i=0;i<circle;i++){
    scanf("%d\n",&points);
    for(j=0;j<points+1;j++){
      vector<int>vv;
      v.push_back(vv);
    }
    for(j=0;j<points-1;j++){
      int p1=2;
      int p2=3;
      cin>>p1>>p2;
      v[p1].push_back(p2);
      v[p2].push_back(p1);
    }
    dfsmax=0;
    DFS(v);
    cout<<dfsmax;
  }
}

/*
1
9
1 2
2 3
3 4
2 5
4 6
5 7
5 8
8 9
*/

---

2. 从最小生成树的性质入手，得到树的末节点（度为2,代码里面是1）带入，减少工作量。

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
#define N 1000
int dfsmax=0,points;
bool isoccupy[N]={false};
int degree[N]={0};
void DFSv(vector<vector<int>>v,int start,int record){
  int i,j;
  isoccupy[start]=true;
  bool signal=false;
  for(i=0;i<v[start].size();i++){
    if(!isoccupy[v[start][i]])
    {
      signal=true;
      DFSv(v,v[start][i],record+1);
    }
  }
  if(signal==false){
    dfsmax=max(dfsmax,record);
  }
  isoccupy[start]=false;
}
void DFS(vector<vector<int>>v){
  int i,j;
  int record=0;
  for(i=1;i<=points;i++){
    if(degree[i]==1){
      DFSv(v,i,record);
    }
  }
}
int main(){
  vector<vector<int>>v;
  int edges,i,j,circle;
  scanf("%d\n",&circle);
  for(i=0;i<circle;i++){
    scanf("%d\n",&points);
    for(j=0;j<points+1;j++){
      vector<int>vv;
      v.push_back(vv);
    }
    for(j=0;j<points-1;j++){
      int p1=2;
      int p2=3;
      cin>>p1>>p2;
      v[p1].push_back(p2);
      v[p2].push_back(p1);
      degree[p1]++;
      degree[p2]++;
    }
    dfsmax=0;
    DFS(v);
    cout<<dfsmax;
  }
}

/*
1
9
1 2
2 3
3 4
2 5
4 6
5 7
5 8
8 9
*/