PAT 甲级 1021 Deepest Root-白红宇

PAT 甲级 1021 Deepest Root

阅读量：4304 次

发布时间：2019-06-06

本文共 2660 字，大约阅读时间需要 8 分钟。

A graph which is connected and acyclic can be considered a tree. The hight 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

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:

51 21 31 42 5

Sample Output 1:

Sample Input 2:

51 31 42 53 4

Sample Output 2:

Error: 2 components

代码：

#include 
     
      using namespace std;const int maxn = 1e5 + 10;int N;vector
      
        v[maxn];int vis[maxn], mp[maxn];int cnt = 0;int depth = INT_MIN;vector
       
         ans;void dfs(int st) {    vis[st] = 1;    for(int i = 0; i < v[st].size(); i ++) {        if(vis[v[st][i]] == 0)            dfs(v[st][i]);    }}void helper(int st, int step) {    if(step > depth) {        ans.clear();        ans.push_back(st);        depth = step;    } else if(step == depth) ans.push_back(st);    mp[st] = 1;    for(int i = 0; i < v[st].size(); i ++) {        if(mp[v[st][i]] == 0)            helper(v[st][i], step + 1);    }}int main() {    scanf("%d", &N);    memset(vis, 0, sizeof(vis));    for(int i = 0; i < N - 1; i ++) {        int a, b;        scanf("%d%d", &a, &b);        v[a].push_back(b);        v[b].push_back(a);    }    for(int i = 1; i <= N; i ++) {        if(vis[i] == 0) {            dfs(i);            cnt ++;        }        else continue;    }    set
        
          s;    int beginn = 0;    helper(1, 1);    if(ans.size() != 0) beginn = ans[0];    for(int i = 0; i < ans.size(); i ++)        s.insert(ans[i]);    if(cnt >= 2)        printf("Error: %d components\n", cnt);    else {        ans.clear();        depth = INT_MIN;        memset(mp, 0, sizeof(mp));        helper(beginn, 1);        for(int i = 0; i < ans.size(); i ++)            s.insert(ans[i]);        for(set
         
          ::iterator it = s.begin(); it != s.end(); it ++)            printf("%d\n", *it);    }    return 0;}

　　第一个 dfs 搜索有多少个连通块 helper 来找树的直径的一个头已知树的直径树上任意一点到的最大距离的另一端一定是树的直径的一个端点两次深搜

希望新年心里多一点温暖吧失去时间就失去再恨再遗憾也是不会回来向前看吧记新年熬第一夜

转载于:https://www.cnblogs.com/zlrrrr/p/10353421.html

你可能感兴趣的文章