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

柔情只为你懂 2022-04-23 07:10 161阅读 0赞

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: ###

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

解题思路:

首先连通分量可以通过广度优先遍历去求,对每一个结点进行广度优先遍历,每一次遍历完成后,使图的连通分量加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;
    }