fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define dbg(x) cout << #x << " : " << x << endl
  5. #define rep(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define inf 1000000000000000000
  7. #define maxn 100005
  8. ll n, m, s, d[maxn] = {inf};
  9. ll dau[maxn] = {0};
  10. vector<ll> edges[maxn];
  11. vector<pair<ll, ll>> res;
  12. queue<ll> q;
  13. void bfs(ll source)
  14. {
  15.     d[source] = 0;
  16.     q.push(source);
  17.     dau[source] = 1;
  18.     while (!q.empty())
  19.     {
  20.         ll p = q.front();
  21.         q.pop();
  22.         for (auto ke : edges[p])
  23.         {
  24.             if (dau[ke] == 1)
  25.                 continue;
  26.             d[ke] = min(d[ke], d[p] + 1);
  27.             q.push(ke);
  28.             dau[ke] = 1;
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     // freopen("input.txt","r",stdin);
  35.     // freopen("output.txt","w",stdout);
  36.     cin >> n >> m >> s;
  37.     s--;
  38.     ll i;
  39.     for (i = 0; i < m; i++)
  40.     {
  41.         ll u, v;
  42.         cin >> u >> v;
  43.         u--, v--;
  44.         edges[u].push_back(v);
  45.         edges[v].push_back(u);
  46.     }
  47.     // for(i=0;i<n;i++){
  48.     //     cout<<i+1<<"-->";
  49.     //     for(auto v: edges[i]) cout<<v+1<<" ";
  50.     //     cout<<'\n';
  51.     // }
  52.     for (i = 0; i < n; i++)
  53.         d[i] = inf;
  54.     bfs(s);
  55.     for (i = 0; i < n; i++)
  56.         res.push_back({d[i], i});
  57.     // cout<<res.size()<<'\n';
  58.     sort(res.begin(), res.end());
  59.     for (auto p : res)
  60.     {
  61.         if (p.first == inf)
  62.             continue;
  63.         cout << p.second + 1 << " " << p.first << '\n';
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 6156KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/fYXcf0
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!