弦图
弦图是一类特殊的无向图。弦图上的所有简单环上都至少有一条弦，其中弦是联结环上两个不相邻的点的边。
这个限制等价于图中存在至少一个完美消除序列。
（好像学了一个没啥用的东西）
完美消除序列
一个完美消除序列是一个排列 $a_1, a_2, \cdots, a_n$，满足对于任意的 $i$，都有 $a_i, a_{i + 1}, \cdots, a_n$ 形成的导出子图中与 $a_i$ 相邻的点两两之间有边。
如何求完美消除序列呢？共有两种算法，可以在 CDQ 的 PPT 中学习，时间复杂度可以做到 $O(n + m)$。
例题
题目大意
给定一个 $n$ 个点 $m$ 条边的弦图，求它的色数。
数据范围：$n \le 10^4, m \le 10^6$。
思路分析
求出一个完美消除序列，然后贪心地倒着染色。不难发现这肯定是对的，因为与当前点相邻的染过色的点的颜色互不相同。
因为图的色数是 $O(\sqrt m)$ 的，所以总共染色的复杂度是 $O(n \sqrt m)$，可以通过本题。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | const int maxn = 2e4; |
5 | int n, m, a[maxn + 3], c[maxn + 3], l[maxn + 3], r[maxn + 3], col[maxn + 3], vis[maxn + 3]; |
6 | bool b[maxn + 3]; |
7 | vector<int> G[maxn + 3]; |
8 | |
9 | void get_array() { |
10 | for (int i = 0; i <= 2 * n; i++) { |
11 | l[i] = r[i] = -1; |
12 | } |
13 | for (int i = 1, t = 0; i <= n; i++) { |
14 | l[n + i] = t, r[t] = n + i, t = n + i; |
15 | } |
16 | int mx = 0; |
17 | for (int k = 1; k <= n; k++) { |
18 | while (r[mx] == -1) { |
19 | mx--; |
20 | } |
21 | int u = r[mx] - n, t = r[u + n]; |
22 | l[t] = mx, r[mx] = t; |
23 | a[k] = u, b[u] = true; |
24 | for (int i = 0, v, lx, rx; i < G[u].size(); i++) { |
25 | v = G[u][i]; |
26 | if (b[v]) { |
27 | continue; |
28 | } |
29 | lx = l[n + v], rx = r[n + v]; |
30 | r[lx] = rx, l[rx] = lx, c[v]++; |
31 | l[n + v] = r[n + v] = -1; |
32 | if (~r[c[v]]) { |
33 | l[r[c[v]]] = n + v, r[n + v] = r[c[v]]; |
34 | } |
35 | r[c[v]] = n + v, l[n + v] = c[v]; |
36 | } |
37 | mx++; |
38 | } |
39 | } |
40 | |
41 | int main() { |
42 | scanf("%d %d", &n, &m); |
43 | for (int i = 1, u, v; i <= m; i++) { |
44 | scanf("%d %d", &u, &v); |
45 | G[u].push_back(v), G[v].push_back(u); |
46 | } |
47 | get_array(); |
48 | int ans = 0; |
49 | for (int _ = 1, i; _ <= n; _++) { |
50 | i = a[_]; |
51 | for (int j = 0; j < G[i].size(); j++) { |
52 | vis[col[G[i][j]]] = i; |
53 | } |
54 | for (int j = 1; j <= n; j++) { |
55 | ans = max(ans, j); |
56 | if (vis[j] != i) { |
57 | col[i] = j; |
58 | break; |
59 | } |
60 | } |
61 | } |
62 | printf("%d\n", ans); |
63 | return 0; |
64 | } |