1003 - Drunk.cpp

#include<bits/stdc++.h>
using namespace std;

#define mx 10005

map<string, int> mp;

string a,b;

int ind[mx] = {0};

vector<int> adj[mx];

void topSort(int n)
{
    for(int i=1; i<=n; i++){

        if(ind[i]==0){

            int sz = adj[i].size();
            for(int j=0; j<sz; j++){
                ind[ adj[i][j] ]--;
            }

            ind[i] = -1;
            i = 0;

        }

    }

}
int main()
{
    //freopen("out.txt","w",stdout);
    int tc,n,x,y;

    scanf("%d",&tc);

    for(int t=1; t<=tc; t++){

        int cunt = 0;
        scanf("%d",&n);

        for(int i=1; i<=n; i++){

            cin>>a>>b;

            if(mp.find(a) != mp.end()){
                x = mp[a];
            }
            else{
                mp[a] = (++cunt);
                x = cunt;
            }

            if(mp.find(b) != mp.end()){
                y = mp[b];
            }
            else{
                mp[b] = (++cunt);
                y = cunt;
            }

            adj[x].push_back(y);

            ind[y]++;
        }

        topSort(cunt);

        bool ans = true;

        for(int i=1; i<=cunt; i++){

            if(ind[i]>0){
                ans = false;
                break;
            }

        }

        printf("Case %d: ",t);
        ans == true ? printf("Yes\n") : printf("No\n");

        if(t != tc){

            mp.clear();

            for(int i=1; i<=cunt; i++){
                ind[i] = 0;
                adj[i].clear();
            }


        }

    }

    return 0;
}