CF1368E Ski Accidents 做题记录

给定一张 $n$ 个点 $m$ 条边的 DAG，每个点出度至多为 $2$。可以删除不超过 $\frac{4}{7}n$ 个点，使得删点后的图中不存在包含三个点的链。

$1 \leq n \leq 2 \times 10^5$。

做题时可以设出一些未知量，写出一些已知条件方便思考。

图中的点一定能分成三个集合：

• 删去的点集 $S$；
• 删完点后没有入度的点集 $A$；
• 删完点后有入度但没有出度的点集 $B$；

注意到原图每个点出度至多为 $2$，所以一定有 $|B|\le 2|A|$。发现只有 $B$ 中点出边指向的点才会删掉，所以有 $|S|\le 2|B|$。那么有 $|S|\le 2|B|\le 4|A|$，即 $|S|$ 最大不超过 $\frac{4}{7}n$。

那么考虑增量构造，遍历每个点：

• 若它没有入边或入边都来自 $S$ 则加入 $A$；
• 若它没有入边来自 $B$ 则加入 $B$；
• 否则加入 $S$；

时间复杂度 $O(n\log n)$（$\log n$ 来自 set），代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

const int S=200005;

int n,m;
vector<int> g[S];
set<int> as,bs,st;

inline void slove()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) g[i].clear();
	as.clear(),bs.clear(),st.clear();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(g[i].size()==0) as.insert(i);
		else
		{
			bool f=false,f2=false;
			for(int v:g[i]) f|=bs.count(v),f2|=as.count(v);
			if(f) st.insert(i);
			else if(f2) bs.insert(i);
			else as.insert(i);
		}
	}
	printf("%d\n",st.size());
	for(int u:st) printf("%d ",u);
	printf("\n");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}