TIOJ 1092 A.跳格子遊戲

[TOPOSORT]

#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define N 100011
#define V 10010
using namespace std;
struct Edge{int a,b;};
bool operator<(Edge e1,Edge e2)
{
    if(e1.a<e2.a)
        return true;
    else if(e1.a==e2.a)
        return (e1.b<e2.b);
    else
        return false;
}
int n,ecnt;
Edge G[N];
int andS[V];
int andE[V];
//TOPO SORT
int Stamp[V];
vector<int> Stk;
bool Visited[V];
void Toposort()
{
    int Time=0;
    Stk.clear();Stk.push_back(1);
    memset(Visited,false,sizeof(Visited));
    while(Stk.size())
    {
        int get=Stk[Stk.size()-1];
        if(Visited[get])
        {
            Time++;
            Stamp[Time]=get;
            Stk.pop_back();
            continue;
        }
        Visited[get]=true;
        if(get<n)
        {
            for(int lx=andS[get];(lx<=andE[get]);lx++)
                if((Visited[G[lx].b]==false))
                    Stk.push_back(G[lx].b);
        }
    }
    return;
}
bool Status[V];
char NAME[2][10]={"Mimi","Moumou"};
int main()
{
    while(scanf("%d %d",&n,&ecnt)&&(n+ecnt))
    {
        memset(andS,-1,sizeof(andS));
        memset(andE,-1,sizeof(andE));
        memset(Status,false,sizeof(Status));
        int i1,i2;
        for(int lx=0;lx<ecnt;lx++)
        {
            scanf("%d %d",&i1,&i2);
            G[lx].a=i1;G[lx].b=i2;
        }
        char ss[40];
        scanf("%s",ss);
        sort(G,G+ecnt);
        for(int lx=0;lx<ecnt;lx++)
        {
            if(andS[G[lx].a]==-1) andS[G[lx].a]=lx;
            andE[G[lx].a]=lx;
        }
        Toposort();
        Status[n]=true;
        for(int lx=2;lx<=n;lx++)
        {
            bool S=false;
            for(int ly=andS[Stamp[lx]];(ly<=andE[Stamp[lx]]);ly++)
                S=(S||Status[G[ly].b]);
            Status[Stamp[lx]]=1-S;
        }
        if(strlen(ss)==4)
            printf("%s\n",NAME[1-Status[1]]);
        else
            printf("%s\n",NAME[Status[1]]);
    }
    return 0;
}