CF1142E - Pink Floyd
https://www.luogu.com.cn/problem/CF1142E
粉边构成 dag 的做法显然。
然后就是不构成 dag，那么我们可以枚举没有遍历到的点求一个 dfs 生成树，dfs 生成树的性质是删掉的边只会是返祖边，返祖边连接的两个点就不会在集合里同时被选中。所以保证了询问时不会询问到有粉色边连接的点。
//CF1142E
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, ind[N], vis[N], vs[N];
vector<int> g[N], G[N];
void dfs(int x){
vis[x] = vs[x] = 1;
for(int i : g[x]){
if(!vs[i]){
G[x].push_back(i);
++ ind[i];
}
if(!vis[i]){
dfs(i);
}
}
vs[x] = 0;
}
bool ask(int x, int y){
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%d", &x);
return x;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i){
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
}
for(int i = 1; i <= n; ++ i){
if(!vis[i]){
dfs(i);
}
}
vector<int> st;
for(int i = 1; i <= n; ++ i){
if(!ind[i]){
st.push_back(i);
}
}
while(st.size() > 1){
int u = *(--st.end()), v = *(----st.end());
if(ask(u, v)){
st.erase(----st.end());
for(int w : G[v]){
if(!(--ind[w])){
st.push_back(w);
}
}
} else {
st.erase(--st.end());
for(int w : G[u]){
if(!(--ind[w])){
st.push_back(w);
}
}
}
}
printf("! %d\n", st[0]);
return 0;
}