fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. int main() {
  6.     ll n,m;
  7.     cin>>n>>m;
  8.     vector<ll> g[n+5];
  9.     ll i=1;
  10.     while(i<=m) {
  11.         ll u,v;
  12.         cin>>u>>v;
  13.  
  14.         g[u].push_back(v);
  15.         g[v].push_back(u);
  16.         i++;
  17.  
  18.     }
  19.  
  20.     queue<ll> q;
  21.     ll src=1;
  22.     q.push(src);
  23.     ll us[n+5]={0};
  24.     us[src]=1;
  25.     ll lvl[n+5]={0};
  26.     lvl[src]=0;
  27.     ll ways[n+5]={0};
  28.     ways[src]=1;
  29.     while(!q.empty()) {
  30.         ll v=q.front();
  31.         q.pop();
  32.  
  33.         for(auto u:g[v]) {
  34.             if(us[u]==0) {
  35.                 q.push(u);
  36.  
  37.                 us[u]=1;
  38.                 lvl[u]=lvl[v]+1;
  39.                 ways[u]=ways[v];
  40.             } 
  41.  
  42.             else if(lvl[v]+1==lvl[u]) {
  43.                 ways[u]+=ways[v];
  44.             }
  45.         }
  46.     }
  47.  
  48.     for(i=1;i<=n;i++) {
  49.         cout<<"1 to node "<<i<<" = "<<ways[i]<<'\n';
  50.  
  51.     }
  52.     return 0;
  53. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5 6
1 2
1 3
2 4
2 5
3 4
3 5
stdout
copy 
1 to node 1 = 1
1 to node 2 = 1
1 to node 3 = 1
1 to node 4 = 2
1 to node 5 = 2
https://ideone.com/et7FIb
language:
C++ (gcc 8.3)
created:
3 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!