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+1];
  9.     ll i=1;
  10.  
  11.     for(int i=1;i<=m;i++){
  12.     	ll u,v;
  13.         cin>>u>>v;
  14.         g[u].push_back(v);
  15.         g[v].push_back(u);
  16.     }
  17.  
  18.     queue<ll> q;
  19.     ll s=1;
  20.     q.push(s);
  21.     ll us[n+1]={0};
  22.     us[s]=1;
  23.     ll lvl[n+1]={0};
  24.     lvl[s]=0;
  25.     ll ways[n+1]={0};
  26.     ways[s]=1;
  27.     while(!q.empty()) {
  28.         ll v=q.front();
  29.         q.pop();
  30.  
  31.         for(auto u:g[v]) {
  32.             if(us[u]==0) {
  33.                 q.push(u);
  34.  
  35.                 us[u]=1;
  36.                 lvl[u]=lvl[v]+1;
  37.                 ways[u]=ways[v];
  38.             } 
  39.  
  40.             else if(lvl[v]+1==lvl[u]) {
  41.                 ways[u]+=ways[v];
  42.             }
  43.         }
  44.     }
  45.  
  46.     for(i=1;i<=n;i++) {
  47.         cout<<"1 to node "<<i<<" = "<<ways[i]<<'\n';
  48.  
  49.     }
  50.     return 0;
  51. }
Success #stdin #stdout 0s 5276KB
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/V46mLk
language:
C++ (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!