Advertisement
Saleh127

BFS

Oct 26th, 2020
65
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. vector<ll>g[10000];
  7. bool v[10000];
  8. ll dis[10000];
  9.  
  10. void bfs(ll r)
  11. {
  12. queue<ll>qq;
  13. v[r]=1;
  14. dis[r]=0;
  15. qq.push(r);
  16. while(!qq.empty())
  17. {
  18.  
  19. ll node=qq.front();
  20.  
  21. qq.pop();
  22.  
  23. for(ll i=0; i<g[node].size(); i++)
  24. {
  25. ll next=g[node][i];
  26.  
  27. if(v[next]==0)
  28. {
  29. v[next]=1;
  30. dis[next]=dis[node]+1;
  31. qq.push(next);
  32. }
  33. }
  34. }
  35. }
  36.  
  37.  
  38. int main()
  39. {
  40. ios_base::sync_with_stdio(0);
  41. cin.tie(0);
  42. cout.tie(0);
  43.  
  44. ll n,m,a,b,i,j,k,l,root;
  45.  
  46. cin>>n>>m;
  47. for(i=0; i<n; i++)
  48. {
  49. g[i].clear();
  50. v[i]=0;
  51. }
  52. for(i=1; i<=m; i++)
  53. {
  54. cin>>a>>b;
  55. g[a].push_back(b);
  56. g[b].push_back(a);
  57. }
  58. cin>>root;
  59.  
  60. bfs(root);
  61.  
  62. cout << "From node " <<root << endl;
  63. for (i = 1; i <= n; i++)
  64. {
  65. cout << "Distance of " << i << " is : " << dis[i] << endl;
  66. }
  67. return 0;
  68. }
  69.  
Advertisement
RAW Paste Data Copied
Advertisement