1021. Deepest Root (25)

2019-11-11 05:08:09

字体：大中小

来源：转载

供稿：网友

开始用各个叶节点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; }}

上一篇：C#集成第三方控件devexpress 15.2安装说明

下一篇：(编程题)5-20 打印九九口诀表