問題: BOJ 4196 — ドミノ · English · 한국어
各テストケースでは、有向グラフが与えられます。ドミノ u を倒すと、有向辺に沿って u から到達できるドミノがすべて倒れます。すべての頂点を倒すために最初に倒すドミノの最小数を求めます。
まず頂点を強連結成分（SCC）に分けます。同じSCC内ではどの頂点からもほかのすべての頂点に到達できるため、その成分のドミノを一つ倒せば成分全体が倒れます。各SCCを一つの頂点にまとめ、異なるSCC間の辺を残すと、縮約グラフ（SCC DAG）ができます。
縮約グラフで入次数が0のSCCには、必ず最初の一押しが必要です。他の成分からそこへ到達できないためです。逆に、入次数0のSCCを一つずつ倒せば十分です。有限DAGの任意の頂点は、ある始点（入次数0の頂点）から到達できます。各頂点から入ってくる辺をたどり続ければ、有限グラフなのでいずれ入次数0の頂点に着くからです。したがって答えは、入次数0のSCCの個数です。
実装では反復型のKosaraju法を使います。最初のDFSでは明示的なスタックで終了順を記録し、逆辺のグラフを終了順の逆順にたどってSCC IDを割り当てます。再帰呼び出しを使わないため、頂点が100,000個ある長い経路でも呼び出しスタックがあふれません。最後に辺を走査し、異なるSCCから辺が入る成分を記録します。各頂点と辺を定数回処理するので、時間計算量は O(V + E)、空間計算量も O(V + E) です。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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);
}
}