TIOJ 1092 A.跳格子遊戲

poao899    540K    15MS    G++     1.11K     2009-11-06 14:37:27                                   .


題目：

給一個DAG 兩個玩家輪流從1向N走每個人每次走一步

誰先到終點就贏了。























解法：

先依該點結束時間戳記，

然後從戳記最小的開始，

檢查每個點能不能走到終點時保持奇數步(即 先手勝)







//**************************************

#include<stdio.h>
struct edge{
	int j;
	edge *next;
}E[100100],*V[10010];
int edgeCnt;
int stamp[10010],ttime,dis[10010];
bool visited[10010];
int n,e,a,b;
char name[2][10]={"Mimi","Moumou"},in[10];
bool first;
void set(int i,int j){
	edge *p=V[i];
	E[edgeCnt].j=j;
	V[i]=&E[edgeCnt];
	E[edgeCnt].next=p;
	edgeCnt++;
}
void topoSort(int now){
	visited[now]=1;
	edge *p=V[now];
	while(p!=NULL){
		if(!visited[p->j]){
			topoSort(p->j);
		}
		p=p->next;
	}
	stamp[ttime++]=now;
}
main(){
	while(scanf("%d%d",&n,&e),n+e){
		//Initialize
		for(int i=0;i<10010;i++){
			V[i]=NULL;
			visited[i]=0;
		}
		ttime=0;
		//Construct a graph
		for(int i=0;i<e;i++){
			scanf("%d%d",&a,&b);
			set(a,b);
		}
		//Name
		scanf("%s",in);
		first = ((in[1]=='i')?0:1);
		//Topological sort
		topoSort(1);
		//
		for(int i=0;i<ttime;i++){
			int now=stamp[i];
			if(now==n)dis[now]=0;
			else{
				edge *p=V[now];
				dis[now]=0;
				while(p!=NULL){
					if(dis[p->j]==0){
						dis[now]=1;
						break;
					}
					p=p->next;
				}
			}
		}
		//Output
		puts(name[first!=dis[1]]);
	}
}