fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13.         Scanner sc = new Scanner(System.in);
  14.         int n = sc.nextInt();
  15.         int e = sc.nextInt();
  16.  
  17.         ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
  18.         for (int i = 0; i <=n; i++) {
  19.             graph.add(new ArrayList<>());
  20.         }
  21.  
  22.         for (int i = 1; i <= e; i++) {
  23.             int u = sc.nextInt();
  24.             int v = sc.nextInt();
  25.             graph.get(u).add(v);
  26.             graph.get(v).add(u);
  27.         }
  28.  
  29.         // BFS
  30.         Queue<Integer> q=new LinkedList<>();
  31.         int [] visited = new int [n+1];
  32.         int node=sc.nextInt();
  33.         int []level=new int [n+5];
  34.         level[1]=0;
  35.         int [] ways=new int[n+5];
  36.         ways[1]=1;
  37.         q.add(1);
  38.         visited[1]=1;
  39.         while(!q.isEmpty()){
  40.             int removed=q.poll();
  41.  
  42.             for(int u : graph.get(removed)){
  43.                 if(visited[u]==0){
  44.                     q.add(u);
  45.                     visited[u]=1;
  46.                     level[u]=level[removed]+1;
  47.                     ways[u]=ways[removed];
  48.                 }else{
  49.                     if(level[removed]+1==level[u]){
  50.                         ways[u]+=ways[removed];
  51.                     }
  52.                 }
  53.             }
  54.         }
  55.         System.out.println(ways[node]);
  56.         sc.close();
  57. 	}
  58. }
Success #stdin #stdout 0.17s 54592KB
comments (?)
stdin 
5 5
1 2
2 3
2 4
3 5
4 5
5
stdout 
2
https://ideone.com/l3wMdk
language:
Java (HotSpot 12)
created:
6 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!