fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define MOD 1000000007
  5.  
  6. int main(){
  7. #ifndef ONLINE_JUDGE
  8.     freopen("input.txt","r",stdin);
  9.     freopen("output.txt","w",stdout);
  10. #endif
  11.  
  12.     ios_base::sync_with_stdio(false);
  13.     cin.tie(NULL); cout.tie(NULL);
  14.     int testcase = 0;
  15.     cin >> testcase;
  16.     while(testcase--){
  17.         int n, m;
  18.         cin >> n >> m;
  19.         vector<vector<int>> G(n+1);  
  20.         for(int i = 1; i <= m; i++){
  21.             int x, y;
  22.             cin >> x >> y;
  23.             if (x <= n && y <= n) {
  24.                 G[x].push_back(y);
  25.                 G[y].push_back(x);  
  26.             }
  27.         }
  28.  
  29.         int source=1;
  30.         queue<int> q;
  31.         q.push(source);
  32.  
  33.         int used[n+1] = {0};  
  34.         used[source] = 1;
  35.  
  36.         int lvl[n+1] = {0}; 
  37.         int ways[n+1] = {0};  
  38.         ways[source] = 1;     
  39.  
  40.         while(!q.empty()){
  41.             int v = q.front();
  42.             q.pop();
  43.  
  44.             for(auto x: G[v]){
  45.                 if(used[x] == 0){  
  46.                     q.push(x);
  47.                     used[x] = 1;
  48.                     lvl[x] = lvl[v] + 1;
  49.                     ways[x] = ways[v];
  50.                 }
  51.                 else if(used[x] == 1 && lvl[v] + 1 == lvl[x]){ 
  52.                     ways[x] = (ways[x] + ways[v]) % MOD;
  53.                 }
  54.             }
  55.         }
  56.         for(int i = 1; i <= n; i++){
  57.             cout << i << " " << ways[i] << "\n";
  58.         }
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
5 6
1 2
1 3
1 5
1 4
3 6
4 7
stdout
copy 
1 1
2 1
3 1
4 1
5 1
https://ideone.com/IstP4t
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!