fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.  
  7.         int n = sc.nextInt();
  8.         int m = sc.nextInt();
  9.  
  10.         List<Integer>[] G = new List[n + 1];
  11.         for (int i = 0; i <= n; i++) {
  12.             G[i] = new ArrayList<>();
  13.         }
  14.  
  15.         for (int i = 0; i < m; i++) {
  16.             int u = sc.nextInt();
  17.             int v = sc.nextInt();
  18.             G[u].add(v);
  19.             G[v].add(u);
  20.         }
  21.  
  22.         int source = 1;
  23.         Queue<Integer> q = new LinkedList<>();
  24.         q.add(source);
  25.  
  26.         int[] used = new int[n + 1];
  27.         used[source] = 1;
  28.  
  29.         int[] lvl = new int[n + 1];
  30.         lvl[source] = 0;
  31.  
  32.         int[] ways = new int[n + 1];
  33.         ways[source] = 1;
  34.  
  35.         while (!q.isEmpty()) {
  36.             int v = q.poll();
  37.  
  38.             for (int u : G[v]) {
  39.                 if (used[u] == 0) {
  40.                     q.add(u);
  41.                     used[u] = 1;
  42.                     lvl[u] = lvl[v] + 1;
  43.                     ways[u] = ways[v];
  44.                 } else if (lvl[v] + 1 == lvl[u]) {
  45.                     ways[u] += ways[v];
  46.                 }
  47.             }
  48.         }
  49.  
  50.         for (int i = 1; i <= n; i++) {
  51.             System.out.println("Number of shortest paths from source-node " + source + " to node " + i + " = " + ways[i]);
  52.         }
  53.  
  54.         sc.close();
  55.     }
  56. }
  57.  
Success #stdin #stdout 0.22s 58972KB
comments (?)
stdin
copy 
5 4 
1 2
2 1
2 4
2 5
1
stdout
copy 
Number of shortest paths from source-node 1 to node 1 = 1
Number of shortest paths from source-node 1 to node 2 = 2
Number of shortest paths from source-node 1 to node 3 = 0
Number of shortest paths from source-node 1 to node 4 = 2
Number of shortest paths from source-node 1 to node 5 = 2
https://ideone.com/6GEIAf
language:
Java (HotSpot 12)
created:
9 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!