fork download
copy 
  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. 	}
  14. }
  15.  
  16. class TestClass {
  17.     public static void main(String args[] ) throws Exception {
  18.         //BufferedReader
  19.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  20.         String input = br.readLine();                // Reading input from STDIN
  21.         String[]  arr = input.split(" ");
  22.         int n = Integer.parseInt(arr[0]);
  23.         int e = Integer.parseInt(arr[1]);
  24.         ArrayList<ArrayList<Integer>> adj  =  new ArrayList<>();
  25.         for(int i  = 0 ; i<=n ; i++){
  26.             adj.add(new ArrayList<Integer>());   //as the nodes are numbered 1 ---- n
  27.         }
  28.  
  29.         //unit weight undirected graph
  30.         for(int i  = 0 ; i<e ; i++){
  31.             input = br.readLine();
  32.             String[] nodes = input.split(" ");
  33.             int u = Integer.parseInt(nodes[0]);
  34.             int v = Integer.parseInt(nodes[1]);
  35.             adj.get(u).add(v);
  36.             adj.get(v).add(u);
  37.         }
  38.  
  39.         input = br.readLine();
  40.         int source = Integer.parseInt(input);
  41.         //find shortest distance of all nodes from the dource node
  42.         int[] sArr = findShortestD(source , adj); //becuase nodes are 1 based
  43.         for(int i = 1 ; i< sArr.length ; i++){
  44.             System.out.print(sArr[i]+ " ");
  45.         }
  46.     }
  47.  
  48.     private static int[] findShortestD(int s , ArrayList<ArrayList<Integer>> adj){
  49.         int n = adj.size();
  50.         int[] dist = new int[n];
  51.         Arrays.fill(dist , Integer.MAX_VALUE);
  52.         dist[s] = 0;
  53.         Queue<Integer> q =  new LinkedList<>();
  54.         q.offer(s);
  55.  
  56.         while(!q.isEmpty()){
  57.             int top = q.poll();
  58.             for(int  neigh : adj.get(top)){
  59.                 int distTon = dist[top] + 1;
  60.                 if(distTon < dist[neigh]){
  61.                     q.offer(neigh);
  62.                     dist[neigh] = dist[top] + 1;
  63.                 }
  64.             }
  65.         }
  66.         return dist;
  67.     }
  68.  
  69. }
  70.  
Success #stdin #stdout 0.08s 54672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Z5qP7n
language:
Java (HotSpot 12)
created:
4 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!