题目描述
Link
Solution
这道题我们可以考虑二分 $X$ 的位置，然后在 check 里面写一个拓扑排序就行了。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 200100
struct Edge {
int v, nx;
}e[MAXN];
int head[MAXN], ecnt, l, r, n, m, d, y, la, top, rs[MAXN], ls[MAXN], ph[MAXN];
std::vector<int> v[MAXN];
void add(int f, int t) {
e[++ecnt] = (Edge) {t, head[f]};
head[f] = ecnt;
}
bool check(int x) {
for (int i = 1; i <= n; i++) {
head[i] = ls[i] = ph[i] = 0;
}
ecnt = 0;
std::priority_queue <int> q;
for (int i = 1; i <= x; i++) {
for (int j = 1; j < (int)v[i].size(); j++) {
add(v[i][j - 1], v[i][j]);
ph[v[i][j]]++;
}
}
for (int i = 1; i <= n; i++) {
if (!ph[i]) q.push(-i);
}
top = 0;
while (!q.empty()) {
int u = q.top();
u = -u;
q.pop();
top++;
for (int i = head[u]; i; i = e[i].nx) {
int to = e[i].v;
ph[to]--;
if (!ph[to]) q.push(-to);
}
}
if (top == n) return 1;
else return 0;
}
void last(int x) {
for (int i = 1; i <= n; i++) {
head[i] = ls[i] = ph[i] = 0;
}
ecnt = 0;
std::priority_queue <int> q;
for (int i = 1; i <= x; i++) {
for (int j = 1; j < (int)v[i].size(); j++) {
add(v[i][j - 1], v[i][j]);
ph[v[i][j]]++;
}
}
for (int i = 1; i <= n; i++) {
if (!ph[i]) q.push(-i);
}
top = 0;
while (!q.empty()) {
int u = q.top();
u = -u;
q.pop();
rs[++top] = u;
for (int i = head[u]; i; i = e[i].nx) {
int to = e[i].v;
ph[to]--;
if (!ph[to]) q.push(-to);
}
printf("%d ", u);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &d);
for (int j = 1; j <= d; j++) {
scanf("%d", &y);
v[i].push_back(y);
}
}
r = m;
l = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
l = mid + 1;
}
else r = mid - 1;
}
last(r);
return 0;
}
|
