Samkit5025

Untitled

Jun 19th, 2022
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> athleticRace(int N,int M,map<int,vector<int>> &hm){
  5. vector<int> dist(M+1,-1);
  6.  
  7. queue<int> q;
  8. q.push(M);
  9. dist[M] =0;
  10.  
  11. while(!q.empty()){
  12. int temp = q.front();
  13. q.pop();
  14.  
  15. for(int i : hm[temp]){
  16. if(dist[i]==-1){
  17. dist[i] = dist[temp]+1;
  18. q.push(i);
  19. }
  20. }
  21. }
  22.  
  23. int max_dist = 0;
  24. set<int> s;
  25. for(int i=1;i<=N;i++){
  26. s.insert(dist[i]);
  27. max_dist = max(max_dist,dist[i]);
  28. }
  29.  
  30. if(s.size()==1){
  31. return {-1};
  32. }
  33.  
  34. vector<int> result;
  35. for(int i=1;i<=N;i++){
  36. if(dist[i] == max_dist){
  37. result.push_back(i);
  38. }
  39. }
  40. return result;
  41. }
  42.  
  43. int main()
  44. {
  45. int N,M;
  46. cin>>N>>M;
  47.  
  48. map<int,vector<int>> hm;
  49.  
  50. for(int i=0;i<M-1;i++){
  51. int a,b;
  52. cin>>a>>b;
  53.  
  54. hm[a].push_back(b);
  55. hm[b].push_back(a);
  56. }
  57.  
  58. vector<int> res = athleticRace(N,M,hm);
  59.  
  60. for(auto i : res){
  61. cout<<i<<" ";
  62. }
  63. cout<<endl;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment