USACO22OPEN-Platinum D

前言（Front talk)

$\qquad$这道题想出了正解！！！ヾ(≧▽≦*)o

$\qquad$但是我不会打 (*╯^╰)

网址（Website）

$\qquad$洛谷： USACO22OPEN Hoof and Brain P

$\qquad$SPOJ：题目详情 - Hoof and Brain - Super

$\qquad$SPOJ：题解 - Hoof and Brain - Super

题目（Problem）

$\qquad$给定一个包含 $N$ 个结点和 $M$ 条边的有向图（$2 \leq N \leq 10^5$, $1 \leq M \leq 2 \cdot 10^5$），Farmer John 的奶牛们喜欢玩以下的双人游戏。

$\qquad$在图中的不同结点上放置两个指示物（可以用一些与奶牛相关的物品代替指示物）。每一回合，一名玩家，脑，选择一个需要沿某一条出边移动的指示物。另一名玩家，蹄，选择沿着哪条出边移动该指示物。两个指示物在任何时刻不允许处于同一个结点上。如果在某些时刻蹄不能做出合法的行动，则脑获胜。如果游戏可以无限进行下去，则蹄获胜。

$\qquad$给定 $Q$ 个询问（$1 \leq Q \leq 10^5$），包含两个指示物所在的初始结点。对于每个询问，输出哪名玩家获胜。

输入格式（Input）

$\qquad$输入的第一行包含 $N$ 和 $M$。

$\qquad$以下 $M$ 行每行包含两个整数 $a$ 和 $b$，表示一条从 $a$ 连向 $b$ 的边。

$\qquad$图中不包含自环或重边。

$\qquad$下一行包含 $Q$。

$\qquad$最后 $Q$ 行每行包含两个整数 $x$ 和 $y$，满足 $1\le x,y\le N$ 以及 $x\neq y$，表示指示物所在的初始结点。

输出格式（Output）

$\qquad$输出一个长为 $Q$ 的字符串，其中字符 B 表示脑获胜，H 表示蹄获胜。

$\qquad$注意：本题的时间限制为 4 秒，通常限制的两倍。

样例（Example）

样例输入

样例输出

BHHB

提示（Notice）

【数据范围】

$\qquad$脑可以通过选择结点 $5$ 赢得第一局游戏；此时蹄将没有合法的行动。

$\qquad$脑可以通过选择结点 $4$ 然后选择结点 $7$ 赢得最后一局游戏；此时蹄没有合法的行动。

$\qquad$蹄赢得其他局游戏。

【测试点性质】

测试点 2-3 满足 $N\le 100$，$M\le 200$。
测试点 4-9 满足 $N\le 5000$。
测试点 10-21 没有额外限制。

题解（Solution）

理清楚思路：

$\qquad$如果“蹄”走到思路，或者两个指示物重合，则“蹄”输。

$\qquad$“蹄”一定不会选没有环的地方走，因为这样它必输

$\qquad$新的定义：必走路径：从点 $x$ 必定能到达点 $y$ ，称路径 $(x,y)$ 为必走路径。

$\qquad$观察易得：如果两个指示物位于同一条必走路径或有任意一个指示物位于死路，则“蹄”必输。

$\qquad$则需要求出所有的必走路径即可。

想清楚做法：

$\qquad$先找出所有出度为 $0$ 的点，反向找到所有的“死路”，并将边删除（先用拓扑排序找出这些点，再用 $set$ 代替 $vector$ 建边，用多余的 $O(logn)$ 时间来去重点和删边）。

$\qquad$考虑用并查集来合并相同的必走路径，使用启发式合并的方法将两个点合并，时间复杂度 $O(nlogn)$ ，具体便是找到所有的出度为 $1$ 的点，那么该点与其指向的点一定处于一条相同的必走路径中，将其加入队列，处理时启发式合并两个点即可，合并后再检查有没有指向该点的点此时的出度也变成了 $1$ 的，若有，加入队列即可。

$\qquad$最后再 $O(1)$ 判断是否有两个指示物位于同一条必走路径或有任意一个指示物位于死路，若为 $true$ 则“脑”必胜，否则“蹄”必胜。

$\qquad$总时间复杂度： $O(mlog_2n+q)$ 。

代码（Code）

#include<bits/stdc++.h>
#include<queue> 
#include<set>
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 101234;
set<int> ft[N],tf[N];
int n,m,Q,inn[N];
int fa[N];

queue<int> q;
void bfs_dead(){
	For(x,1,n) if(ft[x].size()==0) q.emplace(x);
	For(i,1,n) fa[i]=i;
	while(q.size()){
		int x=q.front();q.pop();
		fa[x]=0;//已经死的点没有爸爸 
		for(auto y:tf[x]){
			ft[y].erase(x);
			if(ft[y].empty()) q.emplace(y);
		}
	}
}

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void bfs_scc(){
	For(x,1,n) if(ft[x].size()==1) q.emplace(x);
	while(q.size()){
		int x=q.front();q.pop();
		int y=*ft[x].begin();
//		cout<<x<<' '<<y<<' '<<q.front()<<'\n';
		x=find(x),y=find(y);
		if(x==y) continue;
		if(tf[x].size()>tf[y].size()) swap(x,y);
		for(auto i:tf[x]){
			ft[i].erase(x);
			ft[i].emplace(y);
			tf[y].emplace(i);
			if(ft[i].size()==1) q.emplace(i);
		}fa[x]=y;
	}
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	freopen("hoof.in", "r", stdin);
	freopen("hoof.out", "w", stdout);
	cin>>n>>m;For(i,1,m){
		int x=input(),y=input();
		ft[x].emplace(y);
		tf[y].emplace(x);
	}cin>>Q;
	bfs_dead();
	bfs_scc();
	while(Q--){
		int x=find(input()),y=find(input());
		cout<<(!x || !y || x==y ? 'B' : 'H');
	}return 0;
}