給定$M$組關係$(a, b), (1\le a, b\le N)$滿足$x_a\le x_b$。
構造一個數列$x$有$N$項，滿足：
- 符合所有$M$組關係。
- 最大值為$k$。
- $[1,k]$皆有在數列出現。
並須最大化$k$。
$N, M\le 10^6$
先建一個圖，每組關係$(a, b)$就連一條有向邊從$a$到$b$。
觀察可以發現對於同個scc中的每個點她的值都必須相同。
$proof$
對於任意兩點$(u, v)$，都可以找到$x_u\le x_{s_1}\le x_{s_2}…\le x_v$及$x_v\le x_{t_1}\le x_{t_2}…\le x_u$。因為遞移律及三一律，$x_u=x_v$。
之後拓樸排序就會是一組解!
這裡使用kosaraju來做scc縮點，複雜度$\mathcal{O}(N+M)$。
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
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
signed main() { EmiliaMyWife
int n, m, t = 0;
cin >> n >> m;
vector<int> ans(n + 1);
stack<int> st;
vector<bool> vis(n + 1);
vector<vector<int>> edge(n + 1), redge(n + 1);
for(int i = 0, a, b; i < m; i++) {
cin >> a >> b;
edge[a].push_back(b);
redge[b].push_back(a);
}
const function<void(int)> dfs = [&] (int u) {
if(vis[u])
return;
vis[u] = true;
for(int v : edge[u])
dfs(v);
st.push(u);
};
const function<void(int, int)> dfs2 = [&] (int u, int c) {
if(ans[u])
return;
ans[u] = c;
for(int v : redge[u])
dfs2(v, c);
};
for(int i = 1; i <= n; i++)
dfs(i);
while(!st.empty()) {
if(!ans[st.top()])
dfs2(st.top(), ++t);
st.pop();
}
cout << t << '\n';
for(int i = 1; i <= n; i++)
cout << ans[i] << " \n"[i == n];
}
|