[CF1142E]Pink Floyd

Description

这是一道交互题

有一张n个点的竞赛图，其中有m条边为粉红色，另外的边为绿色

你现在只知道这m条边的方向，你每次可以询问交互库某条绿边的方向

你需要用不超过2n次询问找到一个点x，使得对于其余所有点y，存在一条x到y的颜色相同的路径

n,m<=10^5

Solution

先考虑没有粉色怎么做，这个很简单，直接维护当前的关键点x，对于每个点y询问(x,y)，如果是x->y保留x否则将关键点设为y

有粉色的话我们可以先对于粉图做一遍dfs，找到粉图中的关键点

然后我们需要用绿边把粉图中的所有关键点连起来，这个可以用上面的做法

注意我们要求的路径是同色的，所以当一个关键点被绿边连接之后它就会在粉图中被删除，这时候要重新维护所有的关键点

因为每次询问都会删除一个点，所以询问次数最多为n-1

Code

#include <vector>#include <cstdio>#include <cstring>#include <algorithm>#define fo(i,a,b) for(int i=a;i<=b;i++)#define fd(i,a,b) for(int i=a;i>=b;i--)#define pb(a) push_back(a)using namespace std;int read() {char ch;for(ch=getchar();ch<'0'||ch>'9';ch=getchar());int x=ch-'0';for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x;}int query(int u,int v) {printf("? %d %d\n",u,v);fflush(stdout);return read();}void answer(int v) {printf("! %d\n",v);fflush(stdout);}const int N=1e5+5;int n,m,deg[N],q[N];vector<int> to[N],e[N];bool vis[N],in[N];void dfs(int x) {vis[x]=in[x]=1;for(int z:to[x]) {if (!in[z]) e[x].pb(z),deg[z]++;if (!vis[z]) dfs(z);}in[x]=0;}int main() {n=read();m=read();fo(i,1,m) {int u=read(),v=read();to[u].pb(v);}fo(i,1,n) if (!vis[i]) dfs(i);fo(i,1,n) if (!deg[i]) q[++q[0]]=i;for(;q[0]>1;) {int u=q[q[0]--],v=q[q[0]--];if (!query(u,v)) swap(u,v);q[++q[0]]=u;for(int z:e[v]) if (!(--deg[z])) q[++q[0]]=z;}answer(q[1]);return 0;}