Lightoj 1003 - Drunk（拓扑排序判断是否有环 Map离散化）

题目链接：http://lightoj.com/volume_showproblem.php?problem=1003

题意是有m个关系格式是a b；表示想要和b必须喝a，问一个人是否喝醉就看一个人是否能把所有种类的饮料喝完，能输出Yes，不能输出No；

其实就是有向图判断是否存在环，可以用拓扑排序来求

拓扑排序：每次找到一个入度为0的点加入队列，删除与之相连的边，循环操作，得到的序列就是拓扑序（前面的必须出现在后面的前面）；

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#include<map>
using namespace std;
#define N 21010
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))

vector<vector<int> >G;///有向图；
int cnt, du[N];///cnt表示共有多少种饮料，du[i]表示map离散化后的饮料编号i的入度；

int topo()
{
    queue<int>Q;

    for(int i=1; i<=cnt; i++)
    {
        if(du[i] == 0)
            Q.push(i);
    }
    int num = 0;///已得到的拓扑序序列中的个数；
    while(Q.size())
    {
        num++;
        int u = Q.front(); Q.pop();
        int len = G[u].size(), v;
        for(int i=0; i<len; i++)
        {
            v = G[u][i];
            du[v] --;
            if(du[v] == 0)
                Q.push(v);
        }
    }
    if(num == cnt)///如果得到的和总的相等则不存在环，否则存在；
        return 1;
    return 0;
}

int main()
{
    int T, n, t = 1;

    scanf("%d", &T);

    while(T--)
    {
        scanf("%d", &n);

        G.clear();
        G.resize(n*2+5);

        cnt = 0;
        met(du, 0);

        char s1[20], s2[20];

        map<string, int> M;
        M.clear();

        for(int i=1; i<=n; i++)
        {
            scanf("%s %s", s1, s2);

            if(M[s1] == 0) M[s1] = ++cnt;
            if(M[s2] == 0) M[s2] = ++cnt;

            G[M[s1]].push_back(M[s2]);

            du[M[s2]] ++;
        }

        if( topo() )
            printf("Case %d: Yes\n", t++);
        else
            printf("Case %d: No\n", t++);
    }
    return 0;
}