BOJ. Soccer Tactics (3977)

Problem: BOJ 3977 — Soccer Tactics · 한국어 · 日本語

The graph is divided into strongly connected components (SCCs). In the condensation graph, every SCC is a vertex and every edge between distinct SCCs is directed. The components with indegree zero are exactly the groups that can be reached from no other group. If there is exactly one such source component, all its vertices are the required starting players; if there is more than one, the answer is Confused.

Kosaraju’s algorithm finds the SCCs in two iterative passes. The first pass performs depth-first search on the original graph and records vertices when their exploration finishes. An explicit vertex stack and a per-vertex next-edge index reproduce recursive DFS exit order without using the call stack. The second pass visits vertices in reverse finishing order on the reversed graph; each traversal identifies one SCC.

While reading the edges, the solution stores both graph directions and keeps the original edge list. After assigning SCC IDs, it marks the destination component of every cross-component edge as having incoming edges. It then counts source components and, when there is exactly one, scans vertices in increasing order to print that SCC. This also handles isolated vertices and a graph with no edges: each isolated vertex is its own source SCC.

The algorithm takes O(V + E) time and O(V + E) memory. It uses no recursion, so a chain of 100,000 vertices cannot overflow the call stack. A blank line is emitted between test cases.

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner input = new FastScanner();
        int testCases = input.nextInt();
        StringBuilder answer = new StringBuilder();

        for (int test = 0; test < testCases; test++) {
            int n = input.nextInt();
            int m = input.nextInt();
            ArrayList<Integer>[] graph = new ArrayList[n];
            ArrayList<Integer>[] reverse = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
                reverse[i] = new ArrayList<>();
            }

            int[] from = new int[m];
            int[] to = new int[m];
            for (int i = 0; i < m; i++) {
                int a = input.nextInt();
                int b = input.nextInt();
                from[i] = a;
                to[i] = b;
                graph[a].add(b);
                reverse[b].add(a);
            }

            boolean[] visited = new boolean[n];
            int[] nextEdge = new int[n];
            int[] stack = new int[n];
            int[] order = new int[n];
            int orderSize = 0;

            for (int start = 0; start < n; start++) {
                if (visited[start]) {
                    continue;
                }
                int top = 0;
                stack[0] = start;
                visited[start] = true;
                while (top >= 0) {
                    int node = stack[top];
                    if (nextEdge[node] < graph[node].size()) {
                        int neighbor = graph[node].get(nextEdge[node]++);
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            stack[++top] = neighbor;
                        }
                    } else {
                        order[orderSize++] = node;
                        top--;
                    }
                }
            }

            int[] component = new int[n];
            int componentCount = 0;
            for (int i = orderSize - 1; i >= 0; i--) {
                int start = order[i];
                if (component[start] != 0) {
                    continue;
                }
                int top = 0;
                stack[0] = start;
                component[start] = ++componentCount;
                while (top >= 0) {
                    int node = stack[top--];
                    for (int neighbor : reverse[node]) {
                        if (component[neighbor] == 0) {
                            component[neighbor] = componentCount;
                            stack[++top] = neighbor;
                        }
                    }
                }
            }

            boolean[] hasIncoming = new boolean[componentCount + 1];
            for (int i = 0; i < m; i++) {
                if (component[from[i]] != component[to[i]]) {
                    hasIncoming[component[to[i]]] = true;
                }
            }

            int source = 0;
            int sourceCount = 0;
            for (int id = 1; id <= componentCount; id++) {
                if (!hasIncoming[id]) {
                    source = id;
                    sourceCount++;
                }
            }

            if (test > 0) {
                answer.append('\n');
            }
            if (sourceCount != 1) {
                answer.append("Confused\n");
            } else {
                for (int vertex = 0; vertex < n; vertex++) {
                    if (component[vertex] == source) {
                        answer.append(vertex).append('\n');
                    }
                }
            }
        }

        System.out.print(answer);
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            int value = 0;
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return value;
        }
    }
}