1021.Deepest Root (25)
pat-al-1021
2017-02-04
考點：深搜dfs關于連通分量的計算：從任一點出發開始深搜，結束一次搜索后如果還有點沒被訪問到（即，可以進行多次搜索）說明連通分量不止一個，能進行幾次搜索就有幾個連通分量關于題目要求的找最長的路徑的起始點，參考了：1021. Deepest Root (25)-PAT甲級真題。個人理解：第一次出發開始搜索（不管起始點是哪個節點）所找到的「當前」最長路徑的終點（們），一定是「整個圖」最長路徑的的起始點，所以再以此為起始點去深搜，找到的「當前」最長路徑的終點，也一定是要找的「整個圖」最長路徑的起始點（因為這是無向圖嘛，起點亦是終點，終點亦是起點）。把這些點保存下來，就是要求的節點。還不能理解就自己在草稿紙上畫一畫。不能用數組來存儲邊了，會內存超限，要改用vector關于vector作為二維數組使用：要么聲明時就聲明為vector< vector< int> > e，搭配e.resize(n)來使用；要么聲明時就給定大小vector< int> e[101]，也可作為二維數組用。如果聲明時是一維的，又沒給定大小，就不能作為二維數組用。使用set是因為set能按從小到大的順序去保存放進去的數，不用自己排序了練習了一下迭代器iterator的使用/** * pat-al-1021 * 2017-02-03 * Cpp version * Author: fengLian_s */#include<stdio.h>#include<string>#include<vector>#include<set>#define MAX 10001#define INF 0x3f3f3f3fusing namespace std;int n, visited[MAX];vector<vector<int> > e;int maxDepth = -1;vector<int> v;set<int> s;void dfs(int id, int depth){ visited[id] = 1; if(depth > maxDepth) { maxDepth = depth; v.clear(); v.push_back(id); } else if(depth == maxDepth) { v.push_back(id); } for(int i = 0;i < e[id].size();i++) { if(visited[e[id][i]] == 0) dfs(e[id][i], depth+1); }}int main(){ freopen("in.txt", "r", stdin); scanf("%d", &n); e.resize(n+1); for(int i = 1;i < n;i++) { int node1, node2; scanf("%d%d", &node1, &node2); e[node1].push_back(node2); e[node2].push_back(node1); } int cnt = 0, s1; fill(visited, visited+MAX, 0); for(int i = 1;i <= n;i++) { if(visited[i] == 0) { dfs(i, 0); //-FIN-新聞熱點
疑難解答
