1.题目要求求一个图,以哪个节点作为根生成的树高度最高,不唯一则按照从小到大输出;如果图不是一个连通图,则输出有多少个分支。
2.采用并查集来检测是否存在2个或2个以上集合。
3.使用广度优先搜索进行求多源路径。
4.使用Floyd算法会超出内存(可计算10000*10000的int的大小),使用DFS会出现栈溢出(10000深度太深了)。
A graph which is connected and acyclic can be considered a tree. The height 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 (<=10000) 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
//#include<string> //#include <iomanip> #include<vector> #include <algorithm> //#include<stack> #include<set> #include<queue> #include<map> //#include<unordered_set> //#include<unordered_map> //#include <sstream> //#include "func.h" //#include <list> #include<stdio.h> #include<iostream> #include<string> #include<memory.h> #include<limits.h> using namespace std; class VertexNode{ public: vector<int> list; VertexNode() :list(0){}; }; int findRepresent(int a, int* r) { if (r[a] == a) return a; else { r[a] = findRepresent(r[a], r); return r[a]; } } void dfs(int&node, VertexNode *v, int &maxDeep, int deep, int&root, bool*used, vector<pair<int, int>>&ans) { bool visitedAll = true; for (int i = 0; i < v[node].list.size(); i++) { int p = v[node].list[i]; if (!used[p]) { used[p] = true; visitedAll = false; dfs(p, v, maxDeep, deep + 1, root, used, ans); used[p] = false; } } if (visitedAll&&deep >= maxDeep) { maxDeep = deep; ans.push_back({ root, deep }); } } bool cmp(const pair<int, int>&a, const pair<int, int>&b) { if (a.second>b.second) return true; else if (a.second == b.second && a.first < b.first) return true; else return false; } int main(void) { int nodeNum; cin >> nodeNum; //VertexNode *v = new VertexNode[nodeNum];//节点 vector<VertexNode> v(nodeNum); vector<int> temp(0); for (int i = 0; i < nodeNum - 1; i++) { v[i].list = temp; } int *r = new int[nodeNum];//代表 for (int i = 0; i < nodeNum; i++) r[i] = i; for (int i = 0; i < nodeNum - 1; i++) { int a, b; cin >> a >> b; a--; b--; v[a].list.push_back(b); v[b].list.push_back(a); r[findRepresent(a, r)] = findRepresent(b, r);//合并a和b } int setNum = 0; for (int i = 0; i < nodeNum; i++) {//并查集检测集合数量 if (i == r[i]) setNum++; } delete[]r; if (setNum >= 2) { printf("Error: %d components\n", setNum); return 0; } /*bool *used = new bool[nodeNum]; memset(used, false, sizeof(used));*/ vector<bool> used (nodeNum, false); vector<pair<int, int>> ans(0); int maxDeep = 0; for (int root = 0; root < nodeNum; root++) {//对每一个点使用广度优先搜索,BFS //memset(used, false, sizeof(used)); vector<bool> used = vector<bool>(nodeNum, false); queue<int>q; q.push(root); int total = 1; int total2 = 0; int deep = 0; used[root] = true; //cout << "root:" << root << endl; while (!q.empty()) { deep++; //cout << "layer" << deep << " :"; for (int i = 0; i < total; ++i) { int top = q.front(); q.pop(); for (int j = 0; j < v[top].list.size(); ++j) { int p = v[top].list[j]; if (!used[p]) { //cout << p << " "; used[p] = true; q.push(p); total2++; } } } total = total2; total2 = 0; //cout << endl; } //cout << endl; if (deep >= maxDeep) { maxDeep = deep; ans.push_back({ root, deep }); } } sort(ans.begin(), ans.end(), cmp); for (int i = 0; i < nodeNum; i++) { used[i] = false; } for (int i = 0; i < ans.size(); i++) { if (ans[i].second == maxDeep) { used[ans[i].first] = true; //cout << ans[i].first << endl; } else break; } for (int i = 0; i < nodeNum; i++) { if (used[i]) cout << i + 1 << endl; } return 0; }