CF1368ESkiAccidents

读懂题是第一要素。

考虑把点集分割为:\(A,B,C\)

首先把所有入度为\(0\)的点加入\(A\)

然后对所有入边只来自\(A\)的点加入\(B\)

然后对所有入边只来自\(B\)的点加入\(C\)

剩下的全部加入\(C\)

此时：

A:只有入度为0的点，或者全部入边全来自C

B：只有来自A的入度

C：至少有来自B的入度

那么这要我们删掉C，即可保证没有三点是联通的。

由于每个点只有两个出度，所以我们可以证明，\(|C| \leq \frac{4}{7}n\)

#include
#include
#include
#include
#define ll long long
#define N 200005
ll n,m;
ll t;
std::vectorto[N];
std::vectorans;
int main(){
scanf("%lld",&t);
while(t -- ){
ans.clear();
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= n;++i)
to[i].clear();
for(int i = 1;i <= m;++i){
ll x,y;
scanf("%lld%lld",&x,&y);
to[y].push_back(x);
}
std::vectorcolor(n);
for(int i = 1;i <= n;++i){
for(int j = 0;j int u = to[i][j];
if(color[u] == 1)
color[i] = 2;
if(color[i] != 2 && color[u] == 0)
color[i] = 1;
}
}
for(int i = 1;i <= n;++i)
if(color[i] == 2)
ans.push_back(i);
std::cout< for(int i = 0;i std::cout< puts("");
}
}