Problem: BOJ 4196 — Dominoes · 한국어 · 日本語
Each test case gives a directed graph: pushing domino u makes every domino reachable by following outgoing edges fall. We need the smallest number of initial pushes that can make every vertex fall.
First group vertices into strongly connected components (SCCs). Inside one SCC, every vertex can reach every other vertex, so one push anywhere in that component topples the entire component. If we collapse each SCC to one vertex and keep edges between different SCCs, the resulting condensation graph is a DAG.
An SCC with no incoming edge in the condensation DAG must receive an initial push: no other component can make it fall. Conversely, pushing one vertex in every source SCC is sufficient. Every vertex in a finite DAG is reachable from some source (repeatedly follow incoming edges until none remain), so all components will fall. Thus the answer is exactly the number of source SCCs.
The implementation uses iterative Kosaraju: an explicit DFS stack records vertices in finishing order, then a traversal of the reversed graph assigns SCC IDs in reverse finishing order. It uses no recursive calls, so a chain with 100,000 vertices cannot overflow the call stack. A final edge scan marks which SCCs have incoming edges from other SCCs. Each vertex and edge is processed a constant number of times, giving O(V + E) time and O(V + E) memory.
Java
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;
public class Main {
private static final class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int position;
private int limit;
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;
}
private int read() throws IOException {
if (position == limit) {
limit = input.read(buffer);
position = 0;
if (limit == -1) {
return -1;
}
}
return buffer[position++];
}
}
public static void main(String[] args) throws Exception {
FastScanner input = new FastScanner();
int testCases = input.nextInt();
StringBuilder answer = new StringBuilder();
while (testCases-- > 0) {
int n = input.nextInt();
int m = input.nextInt();
int[] head = new int[n];
int[] reverseHead = new int[n];
Arrays.fill(head, -1);
Arrays.fill(reverseHead, -1);
int[] to = new int[m];
int[] next = new int[m];
int[] reverseTo = new int[m];
int[] reverseNext = new int[m];
for (int edge = 0; edge < m; edge++) {
int from = input.nextInt() - 1;
int destination = input.nextInt() - 1;
to[edge] = destination;
next[edge] = head[from];
head[from] = edge;
reverseTo[edge] = from;
reverseNext[edge] = reverseHead[destination];
reverseHead[destination] = edge;
}
boolean[] visited = new boolean[n];
int[] order = new int[n];
int orderSize = 0;
int[] nodeStack = new int[n];
int[] edgeStack = new int[n];
for (int start = 0; start < n; start++) {
if (visited[start]) {
continue;
}
int top = 0;
nodeStack[0] = start;
edgeStack[0] = head[start];
visited[start] = true;
while (top >= 0) {
int edge = edgeStack[top];
if (edge == -1) {
order[orderSize++] = nodeStack[top--];
continue;
}
edgeStack[top] = next[edge];
int neighbor = to[edge];
if (!visited[neighbor]) {
visited[neighbor] = true;
nodeStack[++top] = neighbor;
edgeStack[top] = head[neighbor];
}
}
}
int[] component = new int[n];
Arrays.fill(component, -1);
int[] stack = new int[n];
int componentCount = 0;
for (int i = orderSize - 1; i >= 0; i--) {
int start = order[i];
if (component[start] != -1) {
continue;
}
int size = 0;
stack[size++] = start;
component[start] = componentCount;
while (size > 0) {
int node = stack[--size];
for (int edge = reverseHead[node]; edge != -1; edge = reverseNext[edge]) {
int neighbor = reverseTo[edge];
if (component[neighbor] == -1) {
component[neighbor] = componentCount;
stack[size++] = neighbor;
}
}
}
componentCount++;
}
boolean[] hasIncoming = new boolean[componentCount];
for (int from = 0; from < n; from++) {
for (int edge = head[from]; edge != -1; edge = next[edge]) {
int sourceComponent = component[from];
int destinationComponent = component[to[edge]];
if (sourceComponent != destinationComponent) {
hasIncoming[destinationComponent] = true;
}
}
}
int pushes = 0;
for (boolean incoming : hasIncoming) {
if (!incoming) {
pushes++;
}
}
answer.append(pushes).append('\n');
}
System.out.print(answer);
}
}