開始用各個葉節點dfs遍歷，找最大deep，運行超時，然后評論里發現個方法，挺贊 https://www.nowcoder.com/questionTerminal/f793ad2e0c7344efa8b6c18d10d4b67b
#include<iostream>#include<algorithm>#include<vector>#define MAX_V 10002using namespace std;vector<int> arc[MAX_V];//相等于鄰接矩陣vector<int> P;//輸出的數組int dis[MAX_V];//相對于root距離int N,dis_max=0;//相對于root最大距離bool visited[MAX_V] = {0};void dfs(int index){ if (dis_max < dis[index]) dis_max = dis[index]; for (auto x : arc[index]) { if (visited[x] == NULL) { dis[x] = dis[index] + 1; visited[x] = true; dfs(x); } }}int main(){ cin >> N; for (int t = 1;t < N;t++) { int i, j; cin >> i >> j; arc[i].push_back(j); arc[j].push_back(i); } int count=0; for (int t = 1;t <= N;t++) { if (visited[t] == false) { dis[t] = 0; visited[t] = true; dfs(t); count++; } } if (count != 1) cout << "Error: " << count << " components" << endl; else { for (int t = 1;t <= N;t++) { if (dis[t] == dis_max) P.push_back(t); visited[t] = false; } visited[P.back()] = true; dfs(P.back()); for (int t = 1;t <= N;t++) { if (find(P.begin(), P.end(), t) == P.end()) if (dis[t] == dis_max) P.push_back(t); } sort(P.begin(), P.end()); for (auto x : P) cout << x << endl; }}新聞熱點
疑難解答
