全面沦陷
题目链接:YBT2023寒假Day5 B
题目大意
给你一个有向图,问你有多少个点可以到达所有点。
一个点 x 能到达一个点 y 当且仅当在原图有路径或在把边反向的图中有路径。
思路
首先我们可以缩点变成一张 DAG。
然后有一个性质,就是把 DAG 的拓扑序求出来,到它的点一定拓扑序比他小,它到的点一定拓扑序比它大。
那两者其实是差不多的,我们考虑拓扑序比他小的。
不如考虑一个点 \(u\) 要怎样才不会被所有比他小的点到达。
设比它小的点中不能到它的编号最大的点是 \(v\),那 \(v+1,v+2,...,u-1\) 都可以到达 \(u\),那 \(v\) 就一定不能到 \(v+1,v+2,...,u-1\)。
那这个也是充要的。
那我们可以定义 \(nxt(x)\) 为 \(x\) 可以到的编号最小的点。(如果没有就是 \(n+1\))
那不能被到达的条件就是存在 \(v<u\) 使得 \(nxt(v)>u\)。
那我们预处理出 \(nxt(x)\) 的话,我们只需要每次把 \([x+1,nxt(x)-1]\) 里面的所有点都标记为有不可达的即可。
(差分一下就可以很快的搞)
然后最后统计可达的就行。(两边的条件记得都要)
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 998244353
using namespace std;
const int N = 1e6 + 100;
struct node {
int to, nxt;
}e[N << 1];
int n, m, le[N], KK, dfn[N], low[N], col[N], sz[N];
int ru[N], sta[N], tot, S, T, id[N], xl[N], pre[N], suf[N];
vector <int> G[N], Gv[N];
pair <int, int> b[N];
ll f[N], g[N];
queue <int> q;
bool yes[N];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void tarjan(int now) {
dfn[now] = low[now] = ++dfn[0]; sta[++sta[0]] = now;
for (int i = le[now]; i; i = e[i].nxt)
if (!dfn[e[i].to]) tarjan(e[i].to), low[now] = min(low[now], low[e[i].to]);
else if (!col[e[i].to]) low[now] = min(low[now], dfn[e[i].to]);
if (dfn[now] == low[now]) {
sz[++tot]++; col[now] = tot;
while (sta[sta[0]] != now) {
sz[tot]++; col[sta[sta[0]]] = tot;
sta[0]--;
}
sta[0]--;
}
}
int main() {
freopen("defeat.in", "r", stdin);
freopen("defeat.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d %d", &x, &y); add(x, y); b[i] = make_pair(x, y);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= m; i++) {
int x = col[b[i].first], y = col[b[i].second];
if (x != y) G[x].push_back(y), ru[y]++, Gv[y].push_back(x);
}
for (int i = 1; i <= tot; i++) if (!ru[i]) q.push(i); int tmp = 0;
while (!q.empty()) {
int now = q.front(); q.pop(); id[now] = ++tmp; xl[tmp] = now;
for (int i = 0; i < G[now].size(); i++) {
int x = G[now][i];
ru[x]--; if (!ru[x]) q.push(x);
}
}
for (int i = 1; i <= tot; i++) {
int to = tot + 1, x = xl[i];
for (int j = 0; j < G[x].size(); j++) {
int y = G[xl[i]][j];
to = min(to, id[y]);
}
pre[x + 1]++; pre[to]--;
to = 0;
for (int j = 0; j < Gv[x].size(); j++) {
int y = Gv[xl[i]][j];
to = max(to, id[y]);
}
suf[x - 1]++; suf[to]--;
}
for (int i = 1; i <= tot; i++) pre[i] = pre[i - 1] + pre[i];
for (int i = tot; i >= 1; i--) suf[i] = suf[i + 1] + suf[i];
int ans = 0;
for (int i = 1; i <= tot; i++)
if (!pre[id[i]] && !suf[id[i]]) ans += sz[i], yes[i] = 1;
printf("%d\n", ans);
for (int i = 1; i <= n; i++)
if (yes[col[i]]) printf("%d ", i);
return 0;
}
标签:tarjan,YBT2023,sta,int,Day5,++,include,low,now
From: https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day5_B.html