fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100005;
  6. int n, m, dis[N], S;
  7. vector<int> dsk[N];
  8. queue<int> Q;
  9.  
  10. pair<int, int> a[N];
  11.  
  12. int main() {
  13. //    freopen("test.inp", "r", stdin);
  14. //    freopen("test.out", "w", stdout);
  15.  
  16.     cin >> n >> m >> S;
  17.     /// n là số lượng đỉnh
  18.  
  19.     /// m là số lượng cạnh
  20.  
  21.     for (int i = 1; i <= m; i++) {
  22.         int u, v;
  23.  
  24.         cin >> u >> v;
  25.  
  26.         /// người ta đang cho em cạnh nối từ u tới v
  27.  
  28.         dsk[u].push_back(v);
  29.  
  30.         dsk[v].push_back(u);
  31.     }
  32.  
  33.     for (int i = 1; i <= n; i++)
  34.         dis[i] = -1;
  35.  
  36.     dis[S] = 0;
  37.     Q.push(S);
  38.  
  39.     while (Q.size()) {
  40.         int u = Q.front();
  41.         /// lay gia tri đầu tiên trong queue
  42.  
  43.         Q.pop();
  44.         /// xoa dinh o dau
  45.  
  46.         for (int v : dsk[u])
  47.             if (dis[v] == -1) {
  48.                 dis[v] = dis[u] + 1;
  49.                 Q.push(v);
  50.             }
  51.     }
  52.  
  53.     for (int i = 1; i <= n; i++) {
  54.         a[i].first = dis[i];
  55.         a[i].second = i;
  56.     }
  57.  
  58.     sort(a + 1, a + n + 1);
  59.  
  60.     for (int i = 1; i <= n; i++) {
  61.         int kc = a[i].first;
  62.         int dinh = a[i].second;
  63.  
  64.         if (kc != -1)
  65.             cout << dinh << " " << kc << endl;
  66.     }
  67.  
  68.  
  69. }
  70.  
Success #stdin #stdout 0.01s 6084KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CyCLb0
language:
C++14 (gcc 8.3)
created:
7 days 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!