题解 CF1142E 【Pink Floyd】
Piwry
2020-10-17 07:36:12
## 解析
我们逐级考虑这个问题
### 没有粉色边的情况
先维护一个列表 $\text{top}$，里面的每个结点都是一颗**仅由绿色边**组成的树的根，且根可以到达树中的每个结点
再记录一个列表 $\text{delete}$，里面的每个结点都是可以被 $\text{top}$ 列表中的某个结点到达的
一开始，显然所有点都应该在 $\text{top}$ 里。每次我们从 $\text{top}$ 中取任意两个点 $u, v$ 询问绿色边的方向。如果边是 $(u, v)$，那么就把 $v$ 放入 $\text{delete}$，$u$ 继续留在 $\text{top}$；反之亦然。如此直到 $\text{top}$ 中只剩下一个结点，显然这个结点就是答案；且询问次数是严格 $n-1$ 次的
（值得一提的是，这种情况下该算法给出的是最优（**询问最少**）的方案）
### 粉色边组成 DAG 的情况
同样维护列表 $\text{top}$ 并记录列表 $\text{delete}$。但我们一开始不能将所有结点都放入 $\text{top}$ 了，否则我们询问的两个结点间可能会**已经有**粉色边了
考虑这样一种做法：初始仅将 DAG 中入度为 $0$ 的结点放入 $\text{top}$；每次将结点放入 $\text{delete}$ 时，就在 DAG 中 “删去” 这个结点，并检测是否有新的入度为 $0$ 的结点，有就将其放入 $\text{top}$
如此直到 $\text{top}$ 中只剩下一个结点时，其余的结点要么在 $\text{delete}$ 里，那么它们可以被 $\text{top}$ 中的结点通过绿色路径到达；要么就在 DAG 未被删除的部分中，可以发现这些结点一定能被 $\text{top}$ 中剩下的那个结点通过粉色路径到达（证明考虑 DAG 的拓扑排序性质；正是 $\text{top}$ 中剩下的那个结点连出的边才使这些结点不被删除）。于是 $\text{top}$ 中剩下的这个结点就是答案；且在最多 $n-1$ 次询问后我们就能给出答案
（这种情况下该算法给出的不一定是最优的方案）
### 任意的情况
这里的做法可能会很多（主要是在一些细节上的差异），但大体都是强联通分量（SCC）缩 DAG 然后再处理。这里就只讲下我实现的做法
一开始我们将图中所有的 SCC 求出，并把每个 SCC 导出子图中所有的边（也就是这些 SCC “内部” 的边）都删掉，这样原图就转化为了 DAG。我们仍按照 DAG 的方式做，但对于每个 SCC，我们至多允许其中的**一个**结点出现在 $\text{top}$ 列表中（为了做到这点，我们可以考虑对每个 SCC 维护一个列表 `scc_list`，其中是该 SCC 中入度已经为 $0$，但因为限制无法放入 $\text{top}$ 的结点）。这样我们就保证了每次询问的两个结点间不会有粉色边
当 $\text{top}$ 中只剩下一个结点时，设其为 $u$，其余的结点要么在 $\text{delete}$ 里，那么它们可以被 $u$ 通过绿色路径到达；要么就在 DAG 未被删除的部分中，或为 $u$ 强联通分量中的结点（注意 $u$ 强联通分量中的部分结点也可能在 $\text{delete}$ 中，不过其实并不需要考虑这个问题），前者一定可以被 $u$ 的**强联通分量**通过粉色路径到达，而后者就在 $u$ 的强联通分量中，显然也可被 $u$ 通过粉色路径到达
这样，我们在至多 $n-1$ 次询问后就能给出答案。注意得出的方案**并不一定**是最优的，不过题目并没有要求方案的最优性
## CODE
$\text{delete}$ 其实并不需要在实现中真的记录；但分析时有这个东西会更好说明些
另外注意询问要换行，且要**先刷新屏幕**再读取回答 \fad
```cpp
#include <cstdio>
#include <cstring>
#include <vector>
using std::vector;
using std::min;
const int MAXN =1e5+20;
/*------------------------------Map------------------------------*/
int first[MAXN], tote;
struct edge{
int to, net;
}e[MAXN];
inline void clear_map(){
tote =0;
memset(first, 0, sizeof(first));
}
inline void addedge(const int &u, const int &v){
++tote;
e[tote].to =v, e[tote].net =first[u];
first[u] =tote;
}
/*------------------------------Scc------------------------------*/
vector<int> scc_list[MAXN];
int scc_id[MAXN], in[MAXN];
/*------------------------------Tarjan------------------------------*/
int dfn[MAXN], low[MAXN], cnt;
int stk[MAXN], stk_top;
bool instk[MAXN];
void tarjan(int u){
low[u] =dfn[u] =++cnt;
stk[stk_top++] =u;
instk[u] =1;
for(int l =first[u]; l; l =e[l].net){
if(!dfn[e[l].to]){
tarjan(e[l].to);
low[u] =min(low[u], low[e[l].to]);
}
else if(instk[e[l].to])
low[u] =min(low[u], dfn[e[l].to]);
}
if(low[u] == dfn[u])
while(stk[stk_top] != u){
scc_id[stk[stk_top-1]] =u;/*姑且就以 u 作为 SCC 颜色*/
instk[stk[stk_top-1]] =0;
--stk_top;
}
}
int tmp_e_u[MAXN], tmp_e_v[MAXN], tmp_e_tot;/*临时存边*/
void rebuild_DAG(int n){
for(int i =1; i <= n; ++i)
for(int l =first[i]; l; l =e[l].net)
if(scc_id[e[l].to] != scc_id[i]){
tmp_e_u[tmp_e_tot] =i;
tmp_e_v[tmp_e_tot] =e[l].to;
++tmp_e_tot;
}
clear_map();
for(int i =0; i < tmp_e_tot; ++i){
addedge(tmp_e_u[i], tmp_e_v[i]);
++in[tmp_e_v[i]];
}
}
/*------------------------------Main------------------------------*/
inline int read(){
int x =0; char c =getchar();
while(c < '0' || c > '9') c =getchar();
while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
return x;
}
int top[MAXN], head, tail;
bool in_top[MAXN];
int main(){
int n =read(), m =read();
for(int i =0; i < m; ++i){
int u =read(), v =read();
addedge(u, v);
}
for(int i =1; i <= n; ++i)
if(!dfn[i])
tarjan(i);
rebuild_DAG(n);
for(int i =1; i <= n; ++i)
if(in[i] == 0){
if(!in_top[scc_id[i]]){
top[tail++] =i;
in_top[scc_id[i]] =1;
}
else
scc_list[scc_id[i]].push_back(i);
}
while(tail-head > 1){
int u =top[head], v =top[head+1];
head +=2;
printf("? %d %d\n", u, v);
fflush(stdout);
if(read() == 0)
u ^=v ^=u ^=v;
top[--head] =u;/*将 u 放回，从 head 加入没有特殊含义*/
in_top[scc_id[v]] =0;
for(int l =first[v]; l; l =e[l].net){
--in[e[l].to];
if(in[e[l].to] == 0){
if(!in_top[scc_id[e[l].to]]){
top[tail++] =e[l].to;
in_top[scc_id[e[l].to]] =1;
}
else
scc_list[scc_id[e[l].to]].push_back(e[l].to);
}
}
if((int)scc_list[scc_id[v]].size() > 0){
top[tail++] =scc_list[scc_id[v]][scc_list[scc_id[v]].size()-1];
scc_list[scc_id[v]].pop_back();
in_top[scc_id[v]] =1;
}
}
printf("! %d", top[head]);
}
```