BFS: Shortest Reach in a Graph

BFS: Shortest Reach in a Graph

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static class Graph {

        ArrayList<ArrayList<Integer>> adj;
        int size;

        public Graph(int size) {
            adj = new ArrayList<ArrayList<Integer>>(size);
            for (int i = 0; i < size; i++)
                adj.add(new ArrayList<Integer>());
            this.size = size;
        }

        public void addEdge(int first, int second) {
            adj.get(first).add(second);
            adj.get(second).add(first);
        }

        public int[] shortestReach(int startId) { // 0 indexed
            int[] dist = new int[this.size];
            Arrays.fill(dist, -1);
            Queue<Integer> q = new LinkedList<Integer>();
            boolean v[] = new boolean[this.size];
            q.add(startId);
            v[startId] = true;
            dist[startId] = 0;

            while (!q.isEmpty()) {
                int current = q.poll();

                for (Integer distNode : adj.get(current)) {
                    if (!v[distNode]) {
                        v[distNode] = true;
                        dist[distNode] = dist[current] + 6;
                        q.add(distNode);
                    }
                }
            }

            return dist;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int queries = scanner.nextInt();

        for (int t = 0; t < queries; t++) {

            // Create a graph of size n where each edge weight is 6:
            Graph graph = new Graph(scanner.nextInt());
            int m = scanner.nextInt();

            // read and set edges
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt() - 1;
                int v = scanner.nextInt() - 1;

                // add each edge to the graph
                graph.addEdge(u, v);
            }

            // Find shortest reach from node s
            int startId = scanner.nextInt() - 1;
            int[] distances = graph.shortestReach(startId);

            for (int i = 0; i < distances.length; i++) {
                if (i != startId) {
                    System.out.print(distances[i]);
                    System.out.print(" ");
                }
            }
            System.out.println();
        }

        scanner.close();
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s