1
\$\begingroup\$

Problem statement

In simple words it say, count total Strongly connected components in the graph.

All edges are undirected. I have the following code that uses kosaraju 2DFS approach.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class AirlineProblem {
    private static boolean[] visited = null;
    private static boolean[] reverseVisited = null;
    private static ArrayList<ArrayList<Integer>> adj = null;
    private static ArrayList<ArrayList<Integer>> adjr = null;
    private static boolean[] indegree0 = null;

    public static void main(String[] args) {
        String[] airports = { "BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA", "LHR", "ORD",
                "SAN", "SFO", "SIN", "TLV", "BUD" };
        String[][] routes = { { "DSM", "ORD" }, { "ORD", "BGI" }, { "BGI", "LGA" }, { "SIN", "CDG" }, { "CDG", "SIN" },
                { "CDG", "BUD" }, { "DEL", "DOH" }, { "DEL", "CDG" }, { "TLV", "DEL" }, { "EWR", "HND" },
                { "HND", "ICN" }, { "HND", "JFK" }, { "ICN", "JFK" }, { "JFK", "LGA" }, { "EYW", "LHR" },
                { "LHR", "SFO" }, { "SFO", "SAN" }, { "SFO", "DSM" }, { "SAN", "EYW" } };
        String startingAirport = "LGA";
        System.out.println(solution(airports, routes, startingAirport));
    }

    public static int solution(String[] airports, String[][] routes, String startingAirport) {
        int n = airports.length;

        HashMap<String, Integer> airportsMap = new HashMap<>();
        for (int i = 0; i < n; ++i)
            airportsMap.put(airports[i], i);

        adj = new ArrayList<>(n);
        adjr = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<Integer>());
            adjr.add(new ArrayList<Integer>());
        }
        for (String[] route : routes) {
            adj.get(airportsMap.get(route[0])).add(airportsMap.get(route[1]));
            adjr.get(airportsMap.get(route[1])).add(airportsMap.get(route[0]));
        }

        visited = new boolean[n];
        reverseVisited = new boolean[n];
        indegree0 = new boolean[n];
        for (int i = 0; i < n; i++)
            if (visited[i] == false)
                dfs1(i);

        int counter = 0;
        for (int i = 0; i < n; ++i)
            if (indegree0[i] == true && airportsMap.get(startingAirport) != i)
                counter++;
        return counter;
    }

    private static void dfs1(int node) {
        visited[node] = true;
        boolean hasParent = false;
        for (int i : adjr.get(node))
            if (visited[i] == false) {
                hasParent = true;
                Arrays.fill(reverseVisited, false);
                dfs1(i);
            }

        if (hasParent == false) {
            indegree0[node] = true;
            reverseVisited[node] = true;
            for (int i : adj.get(node))
                if (reverseVisited[i] == false)
                    dfs2(i);
        }
    }

    private static void dfs2(int node) {
        visited[node] = true;
        reverseVisited[node] = true;
        indegree0[node] = false;
        for (int i : adj.get(node))
            if (reverseVisited[i] == false)
                dfs2(i);
    }
}

I would like review about the efficiency, performance and programming paradigm I used. I would also be interested if some tasks can be automated by using a library.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.