CF1142E Pink Floyd 解题报告

解题报告

CF1142E Pink Floyd解题报告：

更好的阅读体验

题意

• 给定一个 $n$ 个点的竞赛图，边分为粉色和绿色，你知道粉色边的方向，但是不知道绿色边的方向。
• 你可以进行若干次询问，每次你可以获得一条绿色边的方向，你需要在 $2n$ 次询问内找到一个点 $u$ 使得对于每个点 $v$，都有一条 $u$ 到 $v$ 的路径，且路径上每条边颜色相同。（注意，你只能通过粉色边与你询问的绿色边）
• $1\leqslant n\leqslant 10^5$。

分析

比较让人迷惑的题。

考虑没有粉色边的情况，我们维护若干个绿色叶向树，每次合并两个根结点就好了，询问次数 $n-1$。

然后是粉色边形成一个 DAG 的情况，我们考虑对粉色边的图拓扑排序，同时维护一个集合 $A$。一开始把所有入度为 $0$ 的结点放到 $A$ 中，每次取其中两个结点合并，找到删除的那个结点它所有的出边到达的结点放入 $A$ 中，直到 $|A|=1$。

那么最后的点要么在剩下的那个结点的绿色叶向树中，要么可以被剩下的那个结点经过粉色的边到达。

最后是原题的情况，显然我们要对粉色图进行缩点，删除同一个强联通分量之间的边，形成一个 DAG。考虑将入度为 $0$ 的 scc 中任取一个点放入 $A$ 中，每次取 $A$ 中两个结点合并，设删除的结点为 $x$，我们让 $x$ 的 scc 中没有删除过且当前入度为 $0$ 的的任一结点放入 $A$ 中，然后再把 $x$ 所有到达的且当前 scc 没有点在 $A$ 中的结点放入 $A$ 中。不断重复上述步骤直到 $|A|=1$。

设剩下的位置为 $s$，那么被删除的结点一定是 $s$ 绿色叶向树内的。如果没有被删除，那么 $s$ 所在连通块（注意，不是强联通块）之外的连通块的结点一定删完了，且 $s$ 所在连通块其他结点一定可以被 $s$ 通过粉色边到达。

时间复杂度：$O(n+m)$。

代码

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100005;
int n,m,top,dfns,tot;
int dfn[maxn],low[maxn],stk[maxn],vis[maxn],bel[maxn],deg[maxn],inque[maxn];
vector<int>g[maxn],v[maxn],ok[maxn];
queue<int>q;
void tarjan(int x){
    dfn[x]=low[x]=++dfns,stk[++top]=x,vis[x]=1;
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(dfn[y]==0)
            tarjan(y),low[x]=min(low[x],low[y]);
        else if(vis[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int y=0;
        tot++;
        while(y!=x)
            y=stk[top--],bel[y]=tot,vis[y]=0;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)
            tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=0;j<g[i].size();j++){
            int k=g[i][j];
            if(bel[i]!=bel[k])
                v[i].push_back(k),deg[k]++;
        }
    for(int i=1;i<=n;i++)
        if(deg[i]==0){
            if(inque[bel[i]]==0)
                q.push(i),inque[bel[i]]=1;
            else ok[bel[i]].push_back(i);
        }
    while(q.size()>1){
        int x=q.front();
        q.pop();
        int y=q.front();
        q.pop();
        printf("? %d %d\n",x,y),fflush(stdout);
        int z;
        scanf("%d",&z);
        if(z==1)
            swap(x,y);
        q.push(y);
        for(int i=0;i<v[x].size();i++){
            int y=v[x][i];
            deg[y]--;
            if(deg[y]==0){
                if(inque[bel[y]]==0)
                    q.push(y),inque[bel[y]]=1;
                else ok[bel[y]].push_back(y);
            }
        }
        inque[bel[x]]=0;
        if(ok[bel[x]].size())
            inque[bel[x]]=1,q.push(ok[bel[x]].back()),ok[bel[x]].pop_back();
    }
    printf("! %d\n",q.front()),fflush(stdout);
    return 0;
}