(mathcal{Description})
Link.
给定 (n) 个点 (m) 条边的有向弱连通图。称一个点是“好点”当且仅当从该点出发，不存在到同一点的两条不同简单路径。求出所有好点，但若好点个数少于 (n imes 20\%)，仅输出 -1。
多测，(n,sum_{}^{} n le10^5)，(m,sum_{}^{} mle2 imes10^5)。
(mathcal{Solution})
先来想一想如何判断某个点 (r) 是好点。以 (r) 为根建出任意一棵外向生成树，不难发现 (r) 是好点，当且仅当树外不存在横叉边（有向 DFS 树是可能存在横叉边的）。
假设我们已经得到了一点 (r) 为好点，如何判断出其他点是否是好点呢？考虑在刚才那棵外向生成树上的某一非根结点 (u)，若从 (u) 子树内向 (u) 的祖先的返祖边多于一条，就显然不合法，否则若 (u) 能到达最高的祖先合法，(u) 也必然合法。
最后一个问题，怎么找到一个 (r) 呢？考虑到 (20\%) 的限制，随机 (100) 个点进行好点测验，如果都不是好点直接输出 -1。错误率为 (left( frac{4}{5}
ight)^{100})，非常可观。
复杂度 (mathcal O(100sum_{}^{} n))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <random>
inline int rint () {
int x = 0, f = 1; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x * f;
}
template<typename Tp>
inline void wint ( Tp x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
const int MAXN = 1e5, MAXM = 2e5;
int n, m, ecnt, head[MAXN + 5], vtag[MAXN + 5], upc[MAXN + 5], top[MAXN + 5];
bool bad[MAXN + 5];
std::mt19937 rnd ( 20050913 );
struct Edge { int to, nxt; } graph[MAXM + 5];
inline void link ( const int s, const int t ) {
graph[++ ecnt] = { t, head[s] };
head[s] = ecnt;
}
inline bool check ( const int u ) {
vtag[u] = 1;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vtag[v = graph[i].to] ) {
if ( !check ( v ) ) return false;
} else if ( vtag[v] == 2 ) {
return false;
}
}
vtag[u] = 2;
return true;
}
inline void mark ( const int u ) {
top[u] = u;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vtag[v = graph[i].to] ) {
vtag[v] = vtag[u] + 1;
mark ( v ), upc[u] += upc[v];
if ( vtag[top[v]] < vtag[top[u]] ) top[u] = top[v];
} else {
++ upc[u], -- upc[v];
if ( vtag[v] < vtag[top[u]] ) top[u] = v;
}
}
}
inline int spread ( const int u ) {
vtag[u] = 1, bad[u] = upc[u] > 1;
int ret = !( bad[u] |= bad[top[u]] );
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( !vtag[v = graph[i].to] ) {
ret += spread ( v );
}
}
return ret;
}
inline void clear () {
ecnt = 0;
for ( int i = 1; i <= n; ++ i ) {
head[i] = vtag[i] = upc[i] = top[i] = bad[i] = 0;
}
}
int main () {
for ( int T = rint (); T --; ) {
clear ();
n = rint (), m = rint ();
for ( int i = 1, u, v; i <= m; ++ i ) {
u = rint (), v = rint ();
link ( u, v );
}
int rt = 0;
for ( int i = 1; i <= 100 && !rt; ++ i ) {
int u = rnd () % n + 1;
for ( int i = 1; i <= n; ++ i ) vtag[i] = 0;
if ( check ( u ) ) rt = u;
}
if ( !rt ) { puts ( "-1" ); continue; }
for ( int i = 1; i <= n; ++ i ) vtag[i] = 0;
vtag[rt] = 1, mark ( rt );
for ( int i = 1; i <= n; ++ i ) vtag[i] = 0;
int cnt = spread ( rt );
if ( cnt * 5 < n ) { puts ( "-1" ); continue; }
for ( int i = 1, f = 0; i <= n; ++ i ) {
if ( !bad[i] ) {
if ( f ) putchar ( ' ' );
f = 1, printf ( "%d", i );
}
}
putchar ( '
' );
}
return 0;
}
(mathcal{Details})
这种随机乱搞题得放开点脑洞啊，看到这种 (20\%) 之类的奇怪限制就可以往这方面想啦。