lightoj1003

CODE

#include <bits/stdc++.h>
#define CL(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
const int INF = 0x3f3f3f3f;
int n,s,m,t,cnt;
map<string,int>mp;
vector<int>e[10005];
int deg[10005];
void toposort()
{
        int rest=cnt;
        queue<int>q;
        for(int i=0;i<cnt;i++)
        {
                if(!deg[i])q.push(i);
        }
        while(q.size())
        {
                int u=q.front();
                q.pop();
                rest--;
                int len=e[u].size();
                for(int i=0;i<len;i++)
                {
                        int v=e[u][i];
                        deg[v]--;
                        if(!deg[v])q.push(v);
                }
        }
        if(rest)
                cout << "No"<<endl;
        else cout << "Yes"<<endl;
}
int main()
{
        cin >> t;
        for(int nCase=1;nCase<=t;nCase++)
        {
                mp.clear();
                CL(deg,0);
                cnt=0;
                cout << "Case "<<nCase<<": ";
                cin >> n;
                for(int i=0;i<10005;i++)
                        e[i].clear();
                string s1,s2;
                while(n--)
                {
                        cin >> s1>> s2;
                        if(!mp[s1])mp[s1]=cnt++;
                        if(!mp[s2])mp[s2]=cnt++;
                        e[mp[s1]].pb(mp[s2]);
                        deg[mp[s2]]++;
                }
                toposort();
        }

        return 0;
}