CF936B题解

Mar 9, 2018 12:47 · 136 words · 1 minute read 题解 codeforces 拆点 图论

如果图中不存在环,那么直接dfs就可以了。

现在图中有环,我的第一想法是缩点,但是怎么也想不出来……

事实上走环并非是毫无意义的,走一个奇环,路径长的奇偶性改变;走一个偶环,虽然奇偶性不改变,但如果赢不了的话可以一直在上面走。

仔细观察可以发现,重复经过一个点也不是毫无意义的,如果两次经过的时候走过路径的长度奇偶性不同,那两次都是有意义的。

于是可以想到拆点,每个点$s$拆成$s_0$和$s_1$,对于每条边$(s,t)$,变成两条边$(s_0,t_1)$和$(s_1,t_0)$,那么具体走到哪个点上就已经代表了路径长的奇偶性。从$s_0$开始dfs,不经过已经经过的点,如果能走到一个出度为0的$x_1$上,那就能赢,如果遇到一个环,那么至少可以平局。

一开始WA了好久,以后要注意有向图的vis和instack是不一样的,判断有没有发现一个环的时候要用instack来判断。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele int
using namespace std;
#define maxn 200010
#define maxm 400010
struct edge{
	ele v;
	edge *nxt;
}ep[maxm],*ecnt;
ele n,m,s,ans,tmp,prv[maxn];
bool vis[maxn],instack[maxn];
edge *h[maxn];
inline void addedge(ele u,ele v){
	edge *p=ecnt++;
	p->v=v; p->nxt=h[u];
	h[u]=p;
}
void dfs(ele i){
	vis[i]=true;
	instack[i]=true;
	if (!h[i] && (i&1)){
		ans=min(ans,0);
		tmp=i;
	}
	for (edge *j=h[i]; j; j=j->nxt)
		if (!vis[j->v])
			prv[j->v]=i,dfs(j->v);
		else if (instack[j->v]) ans=min(ans,1);
	instack[i]=false;
}
void dfs1(ele i){
	if (!~i) return;
	dfs1(prv[i]);
	if (~prv[i]) putchar(' ');
	printf("%d",(i>>1)+1);
}
int main(){
	scanf("%d%d",&n,&m);
	ecnt=ep; memset(h,0,sizeof(h));
	for (int i=0; i<n; ++i){
		ele c;
		scanf("%d",&c);
		for (int j=0; j<c; ++j){
			ele x;
			scanf("%d",&x); --x;
			addedge(i<<1,x<<1|1);
			addedge(i<<1|1,x<<1);
		}
	}
	scanf("%d",&s); --s;
	memset(vis,0,sizeof(vis));
	memset(instack,0,sizeof(instack));
	memset(prv,-1,sizeof(prv));
	ans=2;
	dfs(s<<1);
	if (!ans){
		puts("Win");
		dfs1(tmp);
		puts("");
	}
	else if (ans==1) puts("Draw");
	else puts("Lose");
	return 0;
}