1021.Deepest Root (25)
pat-al-1021
2017-02-04
考點(diǎn)：深搜dfs關(guān)于連通分量的計(jì)算：從任一點(diǎn)出發(fā)開始深搜，結(jié)束一次搜索后如果還有點(diǎn)沒被訪問到（即，可以進(jìn)行多次搜索）說明連通分量不止一個(gè)，能進(jìn)行幾次搜索就有幾個(gè)連通分量關(guān)于題目要求的找最長(zhǎng)的路徑的起始點(diǎn)，參考了：1021. Deepest Root (25)-PAT甲級(jí)真題。個(gè)人理解：第一次出發(fā)開始搜索（不管起始點(diǎn)是哪個(gè)節(jié)點(diǎn)）所找到的「當(dāng)前」最長(zhǎng)路徑的終點(diǎn)（們），一定是「整個(gè)圖」最長(zhǎng)路徑的的起始點(diǎn)，所以再以此為起始點(diǎn)去深搜，找到的「當(dāng)前」最長(zhǎng)路徑的終點(diǎn)，也一定是要找的「整個(gè)圖」最長(zhǎng)路徑的起始點(diǎn)（因?yàn)檫@是無向圖嘛，起點(diǎn)亦是終點(diǎn)，終點(diǎn)亦是起點(diǎn)）。把這些點(diǎn)保存下來，就是要求的節(jié)點(diǎn)。還不能理解就自己在草稿紙上畫一畫。不能用數(shù)組來存儲(chǔ)邊了，會(huì)內(nèi)存超限，要改用vector關(guān)于vector作為二維數(shù)組使用：要么聲明時(shí)就聲明為vector< vector< int> > e，搭配e.resize(n)來使用；要么聲明時(shí)就給定大小vector< int> e[101]，也可作為二維數(shù)組用。如果聲明時(shí)是一維的，又沒給定大小，就不能作為二維數(shù)組用。使用set是因?yàn)閟et能按從小到大的順序去保存放進(jìn)去的數(shù)，不用自己排序了練習(xí)了一下迭代器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-新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
