立志用最少的代碼做最高效的表達

---

PAT甲級最優題解——>傳送門

---

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤10^?4) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N?1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:
For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.

Sample Input 1:
5
1 2
1 3
1 4
2 5
Sample Output 1:
3
4
5

Sample Input 2:
5
1 3
1 4
2 5
3 4
Sample Output 2:
Error: 2 components

---

題意：給出N，表示N個點，接下來有N-1對數，表示某兩個點間有連接。判斷是否為無環圖， 如果是無環圖，則將它看做一棵樹，求在哪個節點為根節點的情況下，樹最深。 如有并列，則升序輸出根節點。

---

本題是一道細節題。

如果一幅圖是一個無環連通圖，則該圖能構成一棵樹。所以要判斷給出的圖是否是無環連通圖，當然這道題降低了難度，因為題目指定了圖中有N個節點，且只有N-1條邊，那么如果這幅圖是連通的，則必然無環；如果這幅圖不連通，則必然有環。

因此，只需判斷連通分量(連通塊)是否大于1，就可知是否Error。 下面貼出代碼，請讀者自行體會。

---

#include<bits/stdc++.h> using namespace std;const int INF = 1e4+5; //結點的最大數量 vector<vector<int>>graph(INF); bool visit[INF]; int maxlevel[INF], level[INF]; //最大深度、當前深度void DFS(int v, int start) { //深度優先遍歷 visit[v] = true;for(int i : graph[v])if(!visit[i]) {level[i] = level[v] + 1; //當前節點深度為父節點深度+1maxlevel[start] = max(maxlevel[start], level[i]);DFS(i, start); } } int main() {int n; cin >> n;for(int i = 1; i < n; i++) {int a, b; cin >> a >> b;graph[a].push_back(b);graph[b].push_back(a);}int num = 0; //記錄連通分量數量for(int i = 1; i <= n; i++) { //深搜求連通分量數量 if(!visit[i]) {++num; //每進行一次遍歷連通分量數+1DFS(i, i); } } if(num > 1) printf("Error: %d components\n", num);else {for(int i = 1; i <= n; i++) {memset(level, 0, sizeof(level)); //將level數組元素置為0memset(visit, false, sizeof(visit)); //將visit數組元素置為falseDFS(i, i); } vector<int>v; //存儲結果int deepLevel = 0;for(int i = 1; i <= n; i++) if(maxlevel[i] > deepLevel) {v.clear();v.push_back(i);deepLevel = maxlevel[i];} else if(maxlevel[i] == deepLevel)v.push_back(i);for(int i = 0; i < v.size(); i++) printf("%d\n", v[i]);} return 0; }

---

耗時：

總結

以上是生活随笔為你收集整理的【分析】1021 Deepest Root (25 分)【DFS解法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。