CF1142E Pink Floyd 题解

题意：

有一张 $n$ 个点的竞赛图 $G$，其中有 $m$ 条边是粉色的，剩下 $\binom {n}{2} - m$ 条边都是绿色的。你现在已经知道所有 $m$ 条粉色边及其定向，但你不知道绿色边的方向。

你可以向交互库发出不超过 $2 n$ 次询问，每次询问的内容为 “ 询问一条绿色边的方向 “。在询问完毕后，你需要找到一个点 $u$，使得：对于 $G$ 中的任何一个点 $v$，均存在一条从 $u$ 到 $v$ 的 (有向) 路径，满足路径上的所有边同色。

可以证明，对于任何一张竞赛图和任意的边染色方案，这样的点 $v$ 是一定存在的。

输入格式：

第一行包含两个正整数 $n, m (1 \leq n \leq 10^5,~0 \leq m \leq \min \left\{ \binom n2, 10^5 \right\})$，表示竞赛图的点数和粉色边的条数。

接下来的 $m$ 行，每行两个正整数 $u, v~(1 \leq u, v \leq n)$，描述一条粉色的边。

输出格式：

如果你需要询问边 $(u, v)$ 的方向，首先需要保证不存在连接 $u$ 和 $v$ 的粉色边，然后你向标准输出打印 ? u v 并刷新缓存。最后从标准输出中读取一个整数 $x$，如果 $x = 1$ 表示定向为 $u \to v$，如果 $x = 0$ 表示定向为 $v \to u$。

当你已经确定找到满足条件的点 $v$ 时，输出 ! v 并退出程序即可。

$\mathcal{Part\ 1}$

很有意思的图论题。~~评分高应该是因为前面的题难？~~

题目就是要在 $2n$ 次的询问内找出原图的一棵树形图。

因为这是一张竞赛图，所以根据淘汰赛选拔的常识其实就可以想到这题的正解。

$\mathcal{Part\ 2}$

竞赛图，之所以叫竞赛图~~而不叫吊打图~~，就是因为可以存在强连通分量。

这个强连通分量也不是不能理解。~~可以当作 Minecraft 职业战争~~，不同职业均有克与被克的关系。

注意到这个树形图可以多解（~~所以搞了个自适应交互库，不然不好卡是吧~~）

因此在竞赛图中找出一个树形图，就相当于我们只关心某种钦定顺序下的“吊打关系”。

这么想想也是合理的，毕竟不同职业也没有个最强最弱，能不能赢更多的是靠运气（随机的比赛顺序）

相信玩过这种职业类 PVP 游戏的 OIer 应该都能轻松理解吧（

$\mathcal{Part\ 3}$

首先考虑没有粉色边的情况。

我们可以把所有人先拉出来，然后两两比赛，留下胜者。最后只有一个人的时候它就是那个树形图的根。

形式化地，我们维护一个集合 $S$ 表示当前还不在树上的点，每次随便取出两个结点 $u,v$

然后询问 $(u,v)$ 的方向，如果是 $u \to v$ ，就把 $v$ 踢掉，否则踢掉 $u$ 。

接着考虑有粉色边的情况。

对于粉色边构成的强连通分量，根据强连通分量的性质，一定存在树形图。

一个简单的想法直接把原图（粉色边构成的图）变成一个 DAG 。

这里其实并不适用缩点，因为刚才说了，如果 $u$ 吊打 $v$ ，$v$ 吊打 $k$ ，不代表 $u$ 吊打 $k$ 。

那么怎么做呢？

$\mathcal{Part\ 4}$

考虑这样一个算法

把所有入度为 $0$ 的点加入 $S$ （仅考虑粉色边对度数的贡献）
每次还是取出两个结点 $u,v$ ，把 $(u,v)$ 定向，不妨设 $u$ 被留下
接着把所有 $u$ 的粉色出边都删掉，并把此时入度为 $0$ 的点加入 $S$ 。
重复定向（操作2,3）直到只剩一个结点。

正确性很显然（但是其实并不好证明，证明放在文章最后，来自参考文献[1]）

通俗地说，因为每个不在 DAG 上的点都可以被绿色边跑到，所以不会漏掉结点。

而这个删边的过程相当于在那个 DAG 上拓扑，顺便把其他的点给加上去。

时间复杂度 $\mathcal{O}(n+m)$ ，询问次数只有不超过 $n-1$ 次。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() getchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e5+15))


bitset<N> vis,ins;
int n,m,pos=1,head[N],in[N];
struct Edge{ int u,v,next; } e[N * 2];
vector<int> to[N],now;
int ask(int u,int v)
{
    static int t;
    printf("? %lld %lld\n",u,v);
    fflush(stdout); read(t); return t;
}
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Tarjan(int u)
{
    vis[u] = ins[u] = 1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!ins[v]){ to[u].push_back(v); ++in[v]; }
        if(!vis[v]) Tarjan(v);
    }
    ins[u] = 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m);
    for(int i=1,u,v; i<=m; i++)
    { read(u); read(v); addEdge(u,v); }
    for(int i=1; i<=n; i++) if(!vis[i]) Tarjan(i);
    for(int i=1; i<=n; i++) if(!in[i]) now.push_back(i);
    for(int u,v; now.size() > 1; )
    {
        u = now.back(); now.pop_back();
        v = now.back(); now.pop_back();
        if(!ask(u,v)) swap(u,v); now.push_back(u);
        for(auto i : to[v]) if(!(--in[i])) now.push_back(i);
    }
    printf("! %lld\n", now.front());
    return 0;
}