fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const long long MaxN = 1e6 + 5;
  6.  
  7. vector<long long> arr[MaxN];
  8. long long n,m,a,b;
  9. bool visited[MaxN];
  10. long long da[MaxN], db[MaxN];
  11.  
  12. void bfs(long long x, vector<long long> arr[], bool visited[], long long d[])
  13. {
  14.     queue<long long> qu;
  15.  
  16.     qu.push(x);
  17.     visited[x] = true;
  18.  
  19.     while (!qu.empty())
  20.     {
  21.         long long u=qu.front();
  22.         qu.pop();
  23.  
  24.         for (long long v : arr[u])
  25.         {
  26.             if (!visited[v])
  27.             {
  28.                 visited[v] = true;
  29.                 qu.push(v);
  30.                 d[v] = d[u] + 1;
  31.             }
  32.         }
  33.     }
  34. }
  35.  
  36. void input()
  37. {
  38.     cin >> n >> m >> a >> b;
  39.  
  40.     for (long long i=1; i<=m; i++)
  41.     {
  42.         long long u,v;
  43.  
  44.         cin >> u >> v;
  45.  
  46.         arr[u].push_back(v);
  47.         arr[v].push_back(u);
  48.     }
  49. }
  50.  
  51. void solve()
  52. {
  53.     for (long long i=1; i<=n; i++)
  54.     {
  55.         visited[i] = false;
  56.     }
  57.  
  58.     bfs(a, arr, visited, da);
  59.  
  60.     for (long long i=1; i<=n; i++)
  61.     {
  62.         visited[i] = false;
  63.     }
  64.  
  65.     bfs(b, arr, visited, db);
  66.  
  67.     long long res=0;
  68.  
  69.     for (long long i=1; i<=n; i++)
  70.     {
  71.         if (da[i] <= db[i])
  72.         {
  73.             res++;
  74.         }
  75.     }
  76.  
  77.     cout << res;
  78. }
  79.  
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0);
  84.  
  85.     input();
  86.     solve();
  87. }
  88.  
Success #stdin #stdout 0.01s 28916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Pfblar
language:
C++14 (gcc 8.3)
created:
2 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!