【还未找到原题】宝石（GEM）

题意

给定 \(m\) 对关系，表示 \(a\) 比 \(b\) 小，此时问最先确定每一个点的排名的关系最小编号，如果最后还未确定排名，则此点输出-1。
由于没有原题，给个样例：
input:

4 4
2 4
3 1
4 1
2 3

output:

3 4 -1 -1

思路

首先容易想到建有向图，边权就是每一条边的编号。
考虑对于一个确定排名的点 \(u\)，要确定它后面的点都比它大，则需要求它到每一个它后面的点的边权最大值，最后在所有它后面的点取个 \(max\) 就行。
但这样显然超时，考虑到每一个 \(u\) 编号后面的点中所有是由排名大于 \(u\) 的点指向另一个排名大于 \(u\) 的点的边都有可能成为答案边。所以可以简化成对于一个点 \(v\) 且 \(v\) 在 \(u\) 后面，排名不小于 \(u\) 的点指向 \(v\)的取个最小值，最后所有不小于 \(u\) 的点全部取个最大值就可以算出其中一半的答案，这里明显可以用两个 \(set\) 来维护，一个维护每个点的，一个维护整体的。
然后倒着连反边再做一遍可以算出前面的。

code

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define x first
#define y second
#define mp make_pairusing namespace std;const int N = 2e5+5,M = 8e5+5;struct edge{ll u,v;
}g[M];
struct Edge{int to,nxt;int w; 
}e[M];ll n,m;
int head[N];
int tot;
void add_Edge(int u,int v,int w){e[tot].to=v,e[tot].nxt=head[u];e[tot].w=w;head[u]=tot++;
}
ll du[N];
ll res[N],f[N];
set<ll> st[N],p;void init(){tot=0;memset(du,0,sizeof(du));memset(head,-1,sizeof(head));
}
void solve(){init();for(int i=1;i<=m;i++){ll u=g[i].u,v=g[i].v;add_Edge(u,v,i);st[v].insert(i);}queue<ll> q;for(int i=1;i<=n;i++){if(st[i].empty())q.push(i);else p.insert(*st[i].begin());}for(int i=1;i<=n;i++){ll u=q.front();q.pop();if(q.empty()){res[u]+=n-i;if(!p.empty())f[u]=max(f[u],*p.rbegin());}for(int j=head[u];~j;j=e[j].nxt){int v=e[j].to,w=e[j].w;p.erase(*st[v].begin());st[v].erase(w);if(!st[v].empty())p.insert(*st[v].begin());else q.push(v);}}
}
int main() {freopen("gem.in","r",stdin);freopen("gem.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++)cin>>g[i].u>>g[i].v;solve();for(int i=1;i<=m;i++)swap(g[i].u,g[i].v);solve();for(int i=1;i<=n;i++){if(res[i]!=n-1)cout<<"-1 ";else cout<<f[i]<<" ";}return 0;
}