Lightoj1003【判环操作】

题意：

对于n个给出字符串a,b，理解成a在b之前办好这个事情，要求n个给出两个串，a都要在b之前完成；

题意：

所以一旦出现环就不行了；

以前在写最短路的时候，spfa就有一个判环，后来写着写着写到了拓扑排序。。。。。判环就好了；

#include<cstdio>

#include<queue>

#include<map>

#include<string>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const LL mod=1e9+7;

const int N=2e4+10;

struct asd{

    int to;

    int next;

};

asd q[N];

int tol,head[N],num;

int pre[N];

bool spfa()

{

    int k;

    int sum=0;

    for(int i=1;i<=num;i++)

    {

        k=-1;

        for(int j=1;j<=num;j++)

        {

            if(!pre[j])

            {

                k=j;

                sum++;

                pre[j]=-1;

                break;

            }

        }

        if(k==-1)

        {

            if(sum==num)

                return true;

            return false;

        }

        for(int v=head[k];v!=-1;v=q[v].next)

        {

            int i=q[v].to;

            if(pre[i]>0)

                pre[i]--;

        }

    }

}

void add(int a,int b)

{

    q[tol].to=b;

    q[tol].next=head[a];

    head[a]=tol++;

}

map<string,int>mp;

int Getid(char *s)

{

    if(mp.find(s)!=mp.end())

        return mp[s];

    return mp[s]=++num;

}

void init()

{

    num=0;

    memset(pre,0,sizeof(pre));

    mp.clear();

    memset(head,-1,sizeof(head));

    tol=0;

}

int main()

{

    int T,cas=1;

    int x,y;

    char s1[15],s2[15];

    scanf("%d",&T);

    while(T--)

    {

        int m;

        scanf("%d",&m);

        init();

        while(m--)

        {

            scanf("%s%s",s1,s2);

            x=Getid(s1);

            y=Getid(s2);

            add(x,y);

            pre[y]++;

        }

        printf("Case %d: ",cas++);

        if(spfa())

            puts("Yes");

        else

            puts("No");

    }

    return 0;

}