BOJ. Strongly Connected Component (2150)

Problem 2150: Strongly Connected Component

Iterative Kosaraju

Kosaraju’s algorithm finds strongly connected components in two depth-first passes. This implementation uses explicit integer stacks rather than recursive calls, so a path of 10,000 vertices cannot exhaust Java’s call stack.

The first pass traverses the original graph. Each stack frame stores a vertex and the index of its next outgoing edge; when all outgoing edges have been examined, the vertex is appended to finishOrder. This is the same postorder as recursive DFS. The second pass visits vertices in reverse finishing order in the reversed graph. Each such traversal collects exactly one SCC: the finishing order ensures that no uncollected component reachable in the reversed graph can absorb it, while reverse reachability groups all vertices mutually reachable with its start vertex.

Vertices are sorted within each component, then components are sorted by their smallest vertex. The output begins with the component count; each component is printed on one line with its vertices followed by -1, as required by BOJ 2150.

Both traversals inspect every vertex and edge a constant number of times. Sorting costs at most O(V log V) across the components; since components partition the vertices, this is bounded by O(V log V). Total time is O(V + E + V log V) and space is O(V + E).

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int vertexCount = input.nextInt();
        int edgeCount = input.nextInt();

        List<Integer>[] graph = new List[vertexCount + 1];
        List<Integer>[] reversed = new List[vertexCount + 1];
        for (int vertex = 1; vertex <= vertexCount; vertex++) {
            graph[vertex] = new ArrayList<>();
            reversed[vertex] = new ArrayList<>();
        }
        for (int i = 0; i < edgeCount; i++) {
            int from = input.nextInt();
            int to = input.nextInt();
            graph[from].add(to);
            reversed[to].add(from);
        }

        boolean[] visited = new boolean[vertexCount + 1];
        int[] stack = new int[vertexCount];
        int[] nextEdge = new int[vertexCount];
        int[] finishOrder = new int[vertexCount];
        int finishCount = 0;

        for (int start = 1; start <= vertexCount; start++) {
            if (visited[start]) {
                continue;
            }
            int top = 0;
            stack[0] = start;
            nextEdge[0] = 0;
            visited[start] = true;

            while (top >= 0) {
                int vertex = stack[top];
                if (nextEdge[top] < graph[vertex].size()) {
                    int neighbor = graph[vertex].get(nextEdge[top]++);
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        stack[++top] = neighbor;
                        nextEdge[top] = 0;
                    }
                } else {
                    finishOrder[finishCount++] = vertex;
                    top--;
                }
            }
        }

        Arrays.fill(visited, false);
        List<List<Integer>> components = new ArrayList<>();
        for (int i = finishCount - 1; i >= 0; i--) {
            int start = finishOrder[i];
            if (visited[start]) {
                continue;
            }

            List<Integer> component = new ArrayList<>();
            int top = 0;
            stack[0] = start;
            visited[start] = true;
            while (top >= 0) {
                int vertex = stack[top--];
                component.add(vertex);
                for (int neighbor : reversed[vertex]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        stack[++top] = neighbor;
                    }
                }
            }
            Collections.sort(component);
            components.add(component);
        }

        components.sort(Comparator.comparingInt(component -> component.get(0)));
        StringBuilder output = new StringBuilder().append(components.size()).append('\n');
        for (List<Integer> component : components) {
            for (int vertex : component) {
                output.append(vertex).append(' ');
            }
            output.append(-1).append('\n');
        }
        System.out.print(output);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int position;
        private int length;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[position++];
        }

        private int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value;
        }
    }
}