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(); // nodes
  8.         int m = sc.nextInt(); // number of edges
  9.  
  10.         // Adjancecy list representation
  11.         List<Integer>[] G = new List[n+1];
  12.         for (int i = 0; i <= n; i++) {
  13.             G[i] = new ArrayList<>();
  14.         }
  15.  
  16.         // Reading edges and building undirected graph
  17.         for (int i = 0; i < m; i++) {
  18.             int u = sc.nextInt();
  19.             int v = sc.nextInt();
  20.             G[u].add(v);
  21.             G[v].add(u);
  22.         }
  23.  
  24.         Queue<Integer> q = new LinkedList<>();
  25.         int source = sc.nextInt(); // starting node for BFS
  26.         q.add(source);
  27.  
  28.         int[] used = new int[n+1]; // track visited nodes
  29.         used[source] = 1;
  30.  
  31.         int[] lvl = new int[n+1]; // shortest distance from source
  32.         lvl[source] = 0;
  33.  
  34.         // BFS traversal
  35.         while (!q.isEmpty()) {
  36.             int v = q.poll(); // current node and poll removes and return the head of the node
  37.             for (int u : G[v]) { // explore all neighbors
  38.                 if (used[u] == 0) { // visit unvisited neighbor
  39.                     q.add(u);
  40.                     used[u] = 1;
  41.                     lvl[u] = lvl[v] + 1; // distance = parent's distance + 1
  42.                 }
  43.             }
  44.         }
  45.  
  46.         // Output shortest distances from source to all nodes
  47.         for (int i = 1; i <= n; i++) {
  48.             System.out.print(lvl[i] + " ");
  49.         }
  50.     }
  51. }
  52.  
Success #stdin #stdout 0.18s 59100KB
comments (?)
stdin
copy 
5 6
1 2
1 3
2 4
3 4
4 5
3 5
1
stdout
copy 
0 1 1 2 2
https://ideone.com/LnKFTe
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!