[ABC304Ex] Constrained Topological Sort 题解

题意

给定一张有向图 \(G\)，有 \(n\) 个点和 \(m\) 条边，问是否存在一种拓扑序的排列 \(P\) 使得 \(l_{i} \le p_{i} \le r_{i}\)。

思路

首先对于一条边 \(u \to v\)，如果限制满足 \(r_{v}\le r_{u}\) 或者 \(l_{v} \ge l_{u}\) 的话，那么这个限制其实是不完全正确的。因为最终的序列一定是一个拓扑序，所以一定有 \(p_{u} \le p_{v}\)，而题目给定的限制是不一定满足这个条件的。所以应该将限制更改为：

\(l_{v}=\max(l_{v},l_{u} + 1),r_{u}=\min(l_{u},l_{v} + 1)\)。

对于 \(l\) 限制的更改应该在拓扑序上正序更改，而对于 \(r\) 的限制应该在拓扑序上倒序更改，因为前者是从 \(u\) 更新到 \(v\)，而后者是从 \(v\) 更新到 \(u\)。

将限制修改后，考虑贪心。应该按照 \(r\) 从小到大的顺序来选择这些点，对于每一个点 \(u\)，最终 \(u\) 点的位置应该满足 \(p_{u}\ge l_{u}\) 并且 \(p_{u}\) 应该尽量去接近 \(l_{u}\)，因为这样选择位置后可以使后面 \(r\) 的值更大的点有更多的选择空间。这个操作可以用一个 \(set\) 来实现，每一次选择就相当于在 \(set\) 中间做一次二分查找第一个大于 \(l_{u}\) 的数，总时间复杂度 \(O(n \log n)\)。

注意还需要判断这个图是不是一个有向无环图，如果不是的话直接判断为不可能即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 3e5 + 10;
int n,m,x,y,l[MAXN],r[MAXN],head[MAXN],cnt,din[MAXN],a[MAXN],tot,ans[MAXN];
struct Node{int u,v,nxt;}e[MAXN];
set <int> s;
vector <int> v[MAXN];
queue <int> q;
inline void Add(int u,int v){e[++cnt] = {u,v,head[u]};head[u] = cnt;}
signed main()
{
	memset(head,-1,sizeof head);
	cin >> n >> m;
	for(int i = 1;i <= m;i++) cin >> x >> y,Add(x,y),din[y]++;
	for(int i = 1;i <= n;i++) cin >> l[i] >> r[i];
	for(int i = 1;i <= n;i++) if(din[i] == 0) q.push(i);
	while(!q.empty())
	{
		int u = a[++tot] = q.front();q.pop();
		for(int i = head[u]; ~ i;i = e[i].nxt)
		{
			int now = e[i].v;
			l[now] = max(l[now],l[u] + 1);
			if(--din[now] == 0) q.push(now);
		}
	}
	if(tot < n){puts("No");return 0;}
	for(int i = tot;i >= 1;i--)
	{
		int u = a[i];
		for(int j = head[u]; ~ j;j = e[j].nxt)
		{
			int now = e[j].v;
			r[u] = min(r[u],r[now] - 1);
		}
		v[r[u]].emplace_back(u);
	}
	for(int i = 1;i <= n;i++)
	{
		s.insert(i);
		for(int j = 0;j < v[i].size();j++)
		{
			int u = v[i][j];
			auto k = s.lower_bound(l[u]);
			if(k == s.end()){puts("No");return 0;}
			ans[u] = *k,s.erase(k);
		}
	}
	puts("Yes");
	for(int i = 1;i <= n;i++) cout << ans[i] << " ";
	return 0; 
}