fork download 
  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.println("Distance from source node " + source + " to node " + i + " is " + lvl[i] + ".");
  49.  
  50. 			 if (used[i] == 0) {
  51.     			System.out.println("You cannot visit " + i +"from the source node "+source);
  52. 				 } 
  53. 			else {
  54.     			  System.out.println("You can visit " + i +"from the source node "+source);;
  55. 				 }
  56. 		}
  57.  
  58.     }
  59. }
  60.  
Success #stdin #stdout 0.32s 61260KB
comments (?)
stdin 
5 4
1 2
1 3
4 5
2 3
1
stdout 
Distance from source node 1 to node 1 is 0.
You can visit 1from the source node 1
Distance from source node 1 to node 2 is 1.
You can visit 2from the source node 1
Distance from source node 1 to node 3 is 1.
You can visit 3from the source node 1
Distance from source node 1 to node 4 is 0.
You cannot visit 4from the source node 1
Distance from source node 1 to node 5 is 0.
You cannot visit 5from the source node 1
https://ideone.com/HQq5af
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!