(PAT 1021) Deepest Root (广度优先遍历求层数)-蒲公英云

(PAT 1021) Deepest Root (广度优先遍历求层数)

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 N (≤104) 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:

Sample Output 1:

3
4
5

Sample Input 2:

Sample Output 2:

Error: 2 components

解题思路:

首先连通分量可以通过广度优先遍历去求,对每一个结点进行广度优先遍历,每一次遍历完成后,使图的连通分量加1,直到所有结点都被访问过为止

然后是求Deepest root,对每一个结点进行广度优先遍历,得到以该节点出发遍历图所得的到的层数,最后取层数最大的那几个结点即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
//广度优先求高度,广度优先求连通分量
struct nNode {
    int ndata;
    int hights;
};
class Graphic {
public:
    int n;
    vector<int>* edges;
    bool* visited;
    vector<int> res;
public:
    Graphic(int _n) {
        n = _n;
        edges = new vector<int>[n];
        visited = new bool[n];
        memset(visited, 0, n);
    }
    void ginsert(int x, int y) {
        edges[x].push_back(y);   //有向图插入
        edges[y].push_back(x);
    }
    int getComponents() {
        int k = 0;
        queue<int> Bfs_queue;
        for (int i = 1; i <= n-1; ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            Bfs_queue.push(i);
            while (!Bfs_queue.empty()) {
                int tnode = Bfs_queue.front();
                Bfs_queue.pop();
                for (int adj_edge : edges[tnode]) {
                    if (!visited[adj_edge]) {
                        visited[adj_edge] = true;
                        Bfs_queue.push(adj_edge);
                    }
                }
            }
            k++;
        }
        memset(visited, 0, n);
        return k;
    }
    void getHight() {
        int maxHight = 0;
        queue<int> bfs_queue;
        queue<int> layer_queue;
        for (int i = 1; i <= n-1; ++i) {
            int curLayer = 0;
            visited[i] = true;
            bfs_queue.push(i);
            layer_queue.push(curLayer);
            while (!bfs_queue.empty()) {
                int tnode = bfs_queue.front();
                curLayer = layer_queue.front() + 1;
                bfs_queue.pop();
                layer_queue.pop();
                for (int adj_edge : edges[tnode]) {
                    if (!visited[adj_edge]) {
                        visited[adj_edge] = true;
                        bfs_queue.push(adj_edge);
                        layer_queue.push(curLayer);
                    }
                }
            }
            if (curLayer >= maxHight) {
                if (curLayer > maxHight) {
                    maxHight = curLayer;
                    res.clear();
                    res.push_back(i);
                }
                else if (curLayer == maxHight) {
                    res.push_back(i);
                }
            }
            memset(visited, 0, n);
        }
    }
};
int main() {
    int N;
    cin >> N;
    Graphic graJic(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int nx, ny;
        cin >> nx >> ny;
        graJic.ginsert(nx, ny);
    }
    int cop = graJic.getComponents();
    if (cop > 1) {  //直接报错
        printf("Error: %d components\n", cop);
    }
    else {
        graJic.getHight();
        sort(graJic.res.begin(), graJic.res.end());
        for (auto x : graJic.res) {
            cout << x << endl;
        }
    }
    return 0;
}