1021 Deepest Root (25)(25 point(s))
2024-10-18 21:38:09
problem
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
tip
answer
#include <cassert>
#include <set>
#include <iostream>
#include <vector>
#include <cstring>
#define Max 10010
#define fi first
#define se second
using namespace std;
int N;
int Root[Max], V[Max];
vector<int > E[Max];
set<int > S, Last;
set<int>::iterator it;
void Init(){
for(int i = 1; i <= N; i++){
Root[i] = i;
}
}
int Find(int i){
if(Root[i] != i) Root[i] = Find(Root[i]);
return Root[i];
}
void Union(int a, int b){
int ra = Find(a);
int rb = Find(b);
if(ra == rb) return ;
Root[ra] = Find(Root[rb]);
}
int TreeNum() {
int num = 0;
for(int i = 1; i <= N; i++){
if(Root[i] == i) num++;
}
return num;
}
int DFS(int t, int deep, int &maxD){
if(deep > maxD){
maxD = deep;
S.clear();
S.insert(t);
}
if(deep == maxD){
S.insert(t);
}
V[t] = 1;
for(int i = 0; i < E[t].size(); i ++){
if(!V[E[t][i]]){
DFS(E[t][i], deep+1, maxD);
}
}
}
void InitV(){
memset(V, 0, sizeof(V));
}
void PrintStatus(){
for(it = S.begin(); it != S.end(); it++){
cout<<*it<<" ";
}
cout<<endl;
}
int main(){
// freopen("test.txt", "r", stdin) ;
ios::sync_with_stdio(false);
//N<= 10000
cin>>N;
if(N == 0){
assert(false);
cout<<"0"<<endl;
}
Init();
int a, b;
for(int i = 0; i < N-1; i++) {
cin>>a>>b;
E[a].push_back(b);
E[b].push_back(a);
Union(a, b);
}
if(TreeNum() > 1) {
cout<<"Error: "<<TreeNum()<<" components";
}else{
int maxD = 0, deepN;
DFS(1, 0, maxD);
// PrintStatus();
for(it = S.begin(); it != S.end(); it++){
Last.insert(*it);
deepN = *it;
}
maxD = 0;
// cout<<deepN<<endl;
InitV();
DFS(deepN, 0, maxD);
// PrintStatus();
for(it = S.begin(); it != S.end(); it++){
Last.insert(*it);
}
for(it = Last.begin(); it != Last.end(); it++){
cout<<*it<<endl;
}
}
return 0;
}
exprience
- acyclic 无环的
最新文章
- Hibernate —— 检索策略
- C#字节数组转换成字符串
- Writing On-Error Trigger In Oracle Forms
- Flux Demo解析
- [PWA] sw-precache
- Flask web开发 处理Session
- JavaScript对象之关联数组
- 最简单的基于FFmpeg的封装格式处理:视音频分离器简化版(demuxer-simple)
- Perl文件测试操作和stat函数
- 使用js从element的matrix推导transform的scale、rotate 和 translate参数
- OCIlib的几个函数的执行效率(附上pro*c的性能对比)
- python 包详解
- [leetcode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
- TestNG中DataProvider的用法
- 无法启动DISTRIBUTED TRANSACTION COORDINATOR解决方法
- Shell编程(脚本)的经常使用命令和语句
- 1、搭建Struts2开发环境
- Linux之精灵进程
- 用jsp实现省市区三级联动下拉
- Vue 前端路由 vue-router
热门文章
- element-UI 表单图片判空验证问题
- pentaho bi server 配置MySQL数据库
- HDU 3065 病毒侵袭持续中 (AC自动机)
- spfa+差分约束系统(D - POJ - 1201 && E - POJ - 1364&&G - POJ - 1)+建边的注意事项+超级源点的建立
- [转]激活函数ReLU、Leaky ReLU、PReLU和RReLU
- 浅析XSS与XSSI异同
- 2016.6.21——Add Binary
- 2016 最佳 Linux 发行版排行榜【转】
- 十六、springboot整合Spring-data-jpa(二)之通用DAO接口与添加自定义方法
- RabbitMQ--work queues(二)