CF1368E

CF1368E

给定一张 DAG，保证出度不超过 (2)，定义操作为：

• 选择一个点 (x)，删去其所有出边。

选择不超过 (frac{4}{7}n) 个点，使得图上不存在经过超过 (2) 个点的路径。

保证连边为 (x o y(x<y))

(nle 2cdot 10^5)

Solution

条件等价于 (nge frac{7}{4} extrm{size})

考虑将点集分成 (A,B,C) 三个集合使得 (Age frac{1}{2}Bge frac{1}{4}C)，这样 (n=A+B+Cge frac{7}{4}C)

我们需要保留 (A,B) 集合，不妨考虑这样构造，保留所有入度为 (0) 的点作为集合 (A)

将 (A) 的所有出边的点保留，如果一个点是被这类点中其他点指向的点，那么删去其，这样我们得到了集合 (B) 且有 (Ble 2A)

然后我们将 (B) 的出边去重并找到，这样得到了 (C)，我们删去 (C) 中的点。

不难发现，此时 (A,B,C) 三类点对答案均没有影响了，所以我们在图上删除 (A,B,C) 这三个集合即可，对于剩余的子图，递归操作即可。

不难发现，我们消去了 (A+B+C) 个点对答案的影响，但是只删除了 (C) 个点，所以这样构造是合法的。

(Code:)

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define vi vector<int>
#define pb push_back
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 2e5 + 5 ; 
int n, m, cnt, del[N], f[N] ; 
vi G[N] ; 
void solve() {
	n = gi(), m = gi() ; int x, y ; cnt = 0 ;
	rep( i, 1, n ) G[i].clear(), f[i] = del[i] = 0 ;
	rep( i, 1, m ) x = gi(), y = gi(), G[x].pb(y) ; 
	rep( i, 1, n ) {
		if( f[i] == 2 ) { ++ cnt, del[i] = 1 ; continue ; }
		for(int v : G[i]) f[v] = max( f[v], f[i] + 1 ) ;
	}
	printf("%d
", cnt ) ;
	rep( i, 1, n ) if( del[i] ) printf("%d ", i ) ;
	puts("") ; 
}
signed main()
{
	int T = gi() ; 
	while( T-- ) solve() ; 
	return 0 ;
}