CF1608C Game Master
Fan_sheng
2021-12-25 16:12:58
一道比较显然的隐式图问题。
## 转化
我们考虑一种情况：选手 A 想要获胜，但是存在一个选手 B，A 在两个场地中都无法击败 B，那么应该怎么处理呢？
我们需要找到一个选手 C 来击败 B，这样 A 就不需要直接面对 B 了。如果 A 也无法击败 C 呢？
显然，这个问题具有传递性。我们最终的目的就是要找到一条长得像 $A\rightarrow K\rightarrow \cdots \rightarrow D \rightarrow C \rightarrow B$ 一样的链，使得 A 最终能够击败 K，那么 A 就能击败这条链上的所有选手。
## 思路
考虑对于每个选手建一个点，如果 A 能够在任意一个场地中击败 B，我们就从 A 到 B 连一条有向边。如果从 A 出发可以走到某一个点，说明 A 能够击败这个选手。如果从 A 出发可以遍历全图，说明 A 有可能取得冠军。
这样，对图上每个强连通分量 tarjan 缩点后，**有且只有一个点没有入度，只有在这个点内的所有选手可能成为冠军**，我们找到这个点就解决问题。
简单证明一下：如果缩点后，有边 $u \rightarrow v$，v 无论怎样都不可能打败 u ，就不可能是冠军。又因为可以成为冠军的人可以遍历到其他所有节点，那么他们一定被缩在一个点里，这个点没有入度且能遍历到其他所有节点。
## 建边的优化
在真正写代码的时候，我们会发现，如果真的把每个击败关系都建成边，可以达到 $\mathbb O(n^2)$ 的复杂度，需要优化。实际上，考虑以下的情况： 如果有两条边 $A \rightarrow B$ 和 $B \rightarrow C$,由于具有传递性，$ A \rightarrow C$ 这条边建了跟没建一样。
如果我们对 $a_i$ 和 $b_i$ 排序，只连接排序后大小相邻的两个选手之间的边，就能达到优化为 $\mathbb O(n)$ 的效果。
## 代码
习惯压行，看着很丑陋。
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n,head[100005],flag,dfn[100005],low[100005],st[100005],color[100005],timer,cnt;
bool in[100005];
struct star{
int to,nxt;
}edge[400005],po[100005];
inline void add(int u,int v){
edge[++flag]=(star){v,head[u]};head[u]=flag;
}
bool cmp(star a,star b){
return a.nxt<b.nxt;
}
inline void clear(){
memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(head,0,sizeof(head));flag=timer=cnt=0;
}
void tarjan(int id){
dfn[id]=low[id]=++timer,in[id]=1,st[++st[0]]=id;
for(int i=head[id];i;i=edge[i].nxt){
int v=edge[i].to;
if(!dfn[v]){
tarjan(v);low[id]=min(low[id],low[v]);
}
else if(in[v])low[id]=min(low[id],dfn[v]);
}
if(dfn[id]==low[id]){
cnt++;
while(st[st[0]]!=id)color[st[st[0]]]=cnt,in[st[st[0]]]=0,st[0]--;
color[id]=cnt,in[id]=0,st[0]--;
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);clear();
for(int times=1;times<=2;times++){//读入a和b，相当于循环两次
for(int i=1;i<=n;i++){
scanf("%d",&po[i].nxt);po[i].to=i;
}
sort(po+1,po+n+1,cmp);
for(int i=2;i<=n;i++)add(po[i].to,po[i-1].to);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=edge[j].nxt){
int v=edge[j].to;if(color[i]!=color[v])in[color[v]]=1;
//in之前是标记是否在tarjan栈内的，这里被我用来标记是否有入度了
}
for(int i=1;i<=n;i++)putchar(in[color[i]]?'0':'1');putchar('\n');
}
return 0;
}
```