Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> athleticRace(int N,int M,map<int,vector<int>> &hm){
- vector<int> dist(M+1,-1);
- queue<int> q;
- q.push(M);
- dist[M] =0;
- while(!q.empty()){
- int temp = q.front();
- q.pop();
- for(int i : hm[temp]){
- if(dist[i]==-1){
- dist[i] = dist[temp]+1;
- q.push(i);
- }
- }
- }
- int max_dist = 0;
- set<int> s;
- for(int i=1;i<=N;i++){
- s.insert(dist[i]);
- max_dist = max(max_dist,dist[i]);
- }
- if(s.size()==1){
- return {-1};
- }
- vector<int> result;
- for(int i=1;i<=N;i++){
- if(dist[i] == max_dist){
- result.push_back(i);
- }
- }
- return result;
- }
- int main()
- {
- int N,M;
- cin>>N>>M;
- map<int,vector<int>> hm;
- for(int i=0;i<M-1;i++){
- int a,b;
- cin>>a>>b;
- hm[a].push_back(b);
- hm[b].push_back(a);
- }
- vector<int> res = athleticRace(N,M,hm);
- for(auto i : res){
- cout<<i<<" ";
- }
- cout<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment