判断图是否都连接构成树,求使树高最大的根
实际上求图上两点间最大距离
先用并查集判断共有几个部分
bfs求距离
先任取一点开始bfs,得到最远的叶节点
以此叶节点再bfs可得
#include<iostream>
using namespace std;
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<memory.h>
#include<algorithm>
#define MAXV 10001
int dist[MAXV]; // store distance
int points[MAXV]; // store root
vector<int> adj_list[MAXV]; //store neighbor
//return the max distance
int bfs(int start , int V)
{
memset(dist,-1,sizeof(dist));
dist[start] = 0;
queue<int> q;
q.push(start);
int dmax = 0;
while(!q.empty())
{
int now = q.front();
q.pop();
int d = dist[now];
for(int i = 0; i < adj_list[now].size(); i++)
{
//not visit before
if(dist[ adj_list[now][i] ] == -1)
{
dist[ adj_list[now][i] ] = d +1;
q.push(adj_list[now][i]);
}
}
if(d > dmax)
{
dmax = d;
}
}
return dmax;
}
int find(int pos)
{
if(points[pos] == -1)
return pos;
return points[pos] = find(points[pos]);
}
int merge(int a,int b)
{
int roota = find(a);
int rootb = find(b);
if(roota == rootb)
return 0;
points[roota] = rootb;
return 1;
}
int main()
{
int N;
int a;
int b;
cin>>N;
memset(points,-1,sizeof(points));
for(int i=0;i<N-1;i++)
{
cin>>a;
cin>>b;
merge(a,b);
adj_list[a].push_back(b);
adj_list[b].push_back(a);
}
//count components
int cnt = 0;
for(int i=1;i<=N;i++)
{
if(points[i]==-1)
cnt++;
}
set<int> first;
set<int> total;
if(cnt != 1)
{
cout<<"Error: "<<cnt<<" components"<<endl;
return 0;
}
else
{
int dmax = bfs(1,N);
for(int i = 1 ;i <= N;i++ )
{
if(dist[i] == dmax)
{
first.insert(i);
total.insert(i);
}
}
dmax = bfs(*first.begin(),N);
for(int i = 1 ;i <= N;i++ )
{
if(dist[i] == dmax)
{
first.insert(i);
total.insert(i);
}
}
for( set<int>::iterator it = total.begin() ; it != total.end() ; ++it )
{
cout << *it << endl;
}
}
}
分享到:
相关推荐
[865]具有所有最深结点的最小子树|smallest-subtree-with-all-the-deepest-nodes给定一个根为 root 的二叉树,每
even the Mariana Trench, the deepest part of the world’s oceans, has been conquered. But explorer I am, and explorer you will be in this book. While much of the known physical world has been ...
your web server's document root or your public HTML directory: mv drupal-x.x/* drupal-x.x/.htaccess /var/www/html If you would like to have the default English interface translated to a ...
1123.Lowest_Common_Ancestor_of_Deepest_Leaves最深叶节点的最近公共祖先【LeetCo
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves. Recall that: The node of a binary tree is a leaf if and only if it has no children The depth of the root of ...
Form Circle is the circle which defines the deepest points of involute form control of the tooth profile. This circle along with the tooth tip circle (or start of chamfer circle) determines the ...
with the best performance occurring in the deepest architecture we trained, with eleven hidden layers. We evaluate this approach on the publicly available SVHN dataset and achieve over 96% accuracy in...
latent variables in the deepest layer are easy to infer and give a much better representation of each document than Latent Semantic Analysis. When the deepest layer is forced to use a small number ...
DeepState: Symbolic Unit Testing for C and C++ Peter Goodman Trail of Bits, Inc.peter@trailofbits.comAlex Groce School of Informatics, Computing & Cyber SystemsNorthern Arizona University ...
Getting to know mother nature is one of the deepest sentiment offered by us humans.
epic battle through the deepest parts of dependency hell, I threw in the towel. Those had been some of the least inspiring hours of my life. I wanted nothing to do with the project. To make matters ...
In doing so, we focused a lot on providing clear interfaces and their documentation in order to avoid usage errors from the deepest possible layer. Some more features implemented specifically for ...
An ICU and Palliative Care specialist featured in the Oscar-nominated Netflix documentary Extremis offers a framework for a better way to exit life that will change our medical culture at the deepest ...
now the deepest issues are about scaling containers in orchestration environments. Containers are considered in context with Kubernetes. There is no other standard to speak of that can support the ...
Form Circle is the circle which defines the deepest points of involute form control of the tooth profile. This circle along with the tooth tip circle (or start of chamfer circle) determines the limits...
This book challenges, with several powerful arguments, some of our deepest beliefs about rationality, morality, and personal identity. The author claims that we have a false view of our own nature; ...
Dive into the deepest, broadest, introductory ASP.NET coverage available. Be guided by an award winning author who will steadily progress your knowledge from first principles to advanced techniques ...
’ It is with deepest regret that we announce the passing of one of our editors, Dr. Haim Ginott, whose contributions are too numerous to list at this time. Let it suffice to note that a truly ...
’ It is with deepest regret that we announce the passing of one of our editors, Dr. Haim Ginott, whose contributions are too numerous to list at this time. Let it suffice to note that a truly ...
Abstract: Today the on-line shopping is becoming a kind of fashion.People have the deepest impression on the Olympic Games in Beijing.Conbining the favourite of the Olympic items and the fashion ...