题目大意
给定一个 $n$ 个点 $m$ 条边的有向无环图，要求给每条边染成红，蓝，绿三种颜色中的一种，使图中不存在任何长度 $> 40$ 的路径（路径的长度定义为它包含的边数），使得路径上所有的边颜色相同。
数据范围：$n \le 5 \times 10^4, m \le 2 \times 10^5$。
思路分析
考虑按照拓扑序构造。
假设已经得到了图中的一个拓扑序列 $p_1, p_2, \cdots, p_n$。考虑将它们每连续 $40$ 个分成一个小组，每 $40^2 = 1600$ 个分成一个大组。
对于每条边，如果它联结的两个点在同一个小组内部，就染成红色；否则如果它联结的两个点在同一个大组内部，就染成绿色；否则染成蓝色。
不难发现所有红色路径都被限制在在小组内部，所有绿色路径都被限制在大组内部，并且每次必须横跨一个小组，而所有蓝色路径每次必须横跨一个大组，所以每种路径的长度都 $<40$，即该构造是合法的。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | const int maxn = 5e4, maxm = 2e5; |
6 | int n, m, u[maxm + 3], v[maxm + 3], deg[maxn + 3], tot, b1[maxn + 3], b2[maxn + 3]; |
7 | queue<int> Q; |
8 | vector<int> G[maxn + 3]; |
9 | |
10 | int main() { |
11 | scanf("%d %d", &n, &m); |
12 | for (int i = 1; i <= m; i++) { |
13 | scanf("%d %d", &u[i], &v[i]); |
14 | deg[v[i]]++; |
15 | G[u[i]].push_back(v[i]); |
16 | } |
17 | for (int i = 1; i <= n; i++) if (!deg[i]) { |
18 | Q.push(i); |
19 | } |
20 | while (!Q.empty()) { |
21 | int u = Q.front(); |
22 | Q.pop(); |
23 | b1[u] = tot / 40; |
24 | b2[u] = tot / 1600; |
25 | tot++; |
26 | for (int v: G[u]) { |
27 | if (!--deg[v]) { |
28 | Q.push(v); |
29 | } |
30 | } |
31 | } |
32 | for (int i = 1; i <= m; i++) { |
33 | if (b1[u[i]] == b1[v[i]]) { |
34 | puts("R"); |
35 | } else if (b2[u[i]] == b2[v[i]]) { |
36 | puts("G"); |
37 | } else { |
38 | puts("B"); |
39 | } |
40 | } |
41 | return 0; |
42 | } |