문제: BOJ 4196 — 도미노 · English · 日本語
각 테스트 케이스에는 방향 그래프가 주어집니다. 도미노 u를 밀면 방향 간선을 따라 u에서 도달할 수 있는 모든 도미노가 쓰러집니다. 모든 정점을 쓰러뜨리는 데 필요한 최초의 밀기 횟수의 최솟값을 구합니다.
먼저 정점들을 강한 연결 요소(SCC)로 묶습니다. 한 SCC 안에서는 모든 정점이 서로 도달할 수 있으므로, 그 요소 안의 도미노 하나를 밀면 나머지도 모두 쓰러집니다. 각 SCC를 정점 하나로 합치고 서로 다른 SCC 사이의 간선을 유지하면 응축 그래프가 만들어지며, 이 그래프는 DAG입니다.
응축 그래프에서 들어오는 간선이 없는 SCC에는 반드시 직접 밀기가 필요합니다. 다른 SCC에서 이 SCC로 도달할 수 없기 때문입니다. 반대로 모든 진입 차수 0인 SCC에서 하나씩 밀면 충분합니다. 유한 DAG의 모든 정점은 어떤 시작점(진입 간선이 없는 정점)으로부터 도달할 수 있습니다. 각 정점에서 들어오는 간선을 거슬러 올라가면 유한한 그래프이므로 결국 진입 간선이 없는 정점에 도달하기 때문입니다. 따라서 답은 진입 차수가 0인 SCC의 개수입니다.
구현은 반복형 코사라주 알고리즘을 사용합니다. 첫 번째 DFS는 명시적인 스택으로 종료 순서를 기록하고, 역방향 그래프를 종료 순서의 역순으로 순회하여 SCC ID를 부여합니다. 재귀 호출이 없어 정점이 100,000개인 긴 경로에서도 호출 스택이 넘치지 않습니다. 마지막으로 간선을 훑어 다른 SCC에서 들어오는 간선이 있는 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);
}
}