题意:
一种游戏,2个人轮流控制棋子在一块有向图上移动,每次移动一条边,不能移动的人为输,无限循环则为平局,棋子初始位置为$S$
现在有一个人可以同时控制两个玩家,问是否能使得第一个人必胜,并输出一个解,否则判断是否能平局
题解:
看到这个题首先我想到了强连通分量,但是事实证明求出强连通分量,缩点对解决问题没有什么帮助....
能写一些看似正确的算法,但其实是假算法来的..
...........
所以应该先分析策略,肯定是能赢就赢,不能赢就求平局,最后才算输
平局很好判断,有向图上,从$S$点跑一边DFS,如果起点的可达子图包含环,就能平局了,具体方法类似tarjan
其次是判断赢,简单来说就是棋子到达了一个点,路径长度为奇数(可以经过环),且这个点没有出边了
换句话说,对于每一个点,其实有2种情况,第一个情况是你到达了这个点,到起点的距离是偶数,那肯定不会是终点了
第二个情况是你到达了这个点,到起点的距离是奇数,这时候如果还没有出边,那就是答案了,保存当前这个函数堆栈里的点即可
可是,问题在于,你可以经过一个环,来使得距离变为奇数,没法简单的DFS
我们考虑,到达每个点时有两种情况,那就是距离起点的距离奇/偶,因此考虑拆点
把每个点拆开,分别代表奇点和偶点,每次加边的时候,把点一分为三
$[1,n]$偶数点,$[n+1,2*n]$ 奇数点 $[2n+1,3n]$ 原图
对于输入的边$(a,b)$,先保存原图,再连2条边,$(a,b+n),(a+n,b)$ 表示如果当前点是偶数距离,距离加一就会变成奇数,反之亦然
意义在于,这个新的图包含了将"绕一个奇数长度的环,将偶数距离变成奇数距离"这种操作
如果是奇数长度的环,在环路的尽头会连接到另外一个偶数距离,而偶数长度的环,则不连通
然后就$O(2(m+n))$的DFS即可
我试着把判环和找答案放在一个DFS里,但是不太好写,容易TLE,就分开了,判环用原图,找答案用拆点的图
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)
using namespace std;
const int maxn=6e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
int casn,n,m,k;
int head[maxn],nume;
struct node {int to,next;} e[maxm];
void add(int a,int b) {
e[++nume]=(node) {b,head[a]};
head[a]=nume;
}
int flag=0,draw=0;
int top,ans[maxn],s,vis[maxn];
void dfs(int now) {
int cnt=0;
vis[now]=1;
ans[++top]=now;
for(int i=head[now]; i; i=e[i].next) {
int to=e[i].to;
if(flag) return;
if(!vis[to])dfs(to);
cnt++;
}
if(now>n&&cnt==0)flag=1;
if(flag==0)top--;
}
int dfs2(int now){
if(vis[now]==2) return 1;
vis[now]=2;
for(int i=head[now];i;i=e[i].next){
int to=e[i].to;
if(!vis[to]){
if(dfs2(to))return 1;
}
else if(vis[to]==2) return 1;
}
vis[now]=1;
return 0;
}
int main() {
IO;
cin>>n>>m;
rep(i,1,n) {
int a,b;
cin>>a;
while(a--) {
cin>>b;
add(i+2*n,b+2*n);
add(i,b+n);
add(i+n,b);
}
}
cin>>s;
draw=dfs2(s+2*n);
top=0;
memset(vis,0,sizeof vis);
dfs(s);
if(flag) {
cout<<"Win\n";
for(int i=1; i<=top; i++) {
cout<<(ans[i]>n? ans[i]-n:ans[i])<<' ';
}
cout<<endl;
} else if(draw) cout<<"Draw\n";
else cout<<"Lose\n";
return 0;
}