LOJ - 1003.cpp

#include <bits/stdc++.h>

using namespace std;

#define zero(arr) memset(arr,0,sizeof(arr));
#define mem(arr,k) memset(arr,k,sizeof(arr));

#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1(i,n) for(int i=1;i<n;i++)
#define FOR(i,m,n,k) for(int i=m;i<n;i=i+k)

#define VI         vector<int>
#define VVI        vector< VI >
#define VIit       VI::iterator
#define pi        pair<int,int>
#define ui64       unsigned long long int
#define i64        long long int
#define pb(a)      push_back(a)
#define mp         make_pair


#define SI(a)      scanf("%d",&a)
#define Si(a)      scanf("%d",&a)
#define SU(a)      scanf("%u",&a)
#define SHD(a)     scanf("%hd",&a)
#define SHU(a)     scanf("%hu",&a)
#define SLLD(a)    scanf("%lld",&a)
#define SLLU(a)    scanf("%llu",&a)
#define SF(a)      scanf("%f",&a)
#define SLF(a)     scanf("%lf",&a)
#define SC(a)      scanf("%c",&a)
#define SS(a)      scanf("%s",a)
#define read       freopen("in.txt","r",stdin)
#define write      freopen("out.txt","w",stdout)
#define PI         acos(-1.0)
#define eps        1e-9

//bool CHECK(int num,int pos){ return num&(1<<(pos)); }
//int SET(int &num,int pos){ return num=(1<<(pos));}
//int CLEAR(int &num,int pos) {return num&=~(1<<(pos));}
//int TOGGLE(int num,int pos) {return num^=(1<<(pos)); }

#define fi          first
#define se          second
#define en          end()
#define ALL(x)      (x).begin(), (x).end()
#define TR(i,x)     for(typeof(x.begin()) i=x.begin();i!=x.end();++i)
#define SZ(x)       (int)(x.size())
bool visited[10000+2];
bool backedge[10000+2];
vector<int>G[10000+2];
bool flag=1;
bool dfs(int node, bool visit[],bool bg[]) {
    if(!visit[node]) {
        visit[node]=1;
        bg[node]=1;
        for(int i=0; i<G[node].size(); i++) {
            int dest = G[node][i];
            if(!visit[dest] && dfs(dest,visit,bg))
                return true  ;
            else if(bg[dest])return true;
        }
    }
    bg[node]=false;
    return false;
}
int main() {
    int t,m;
    cin>>t;
    for(int i=1; i<=t; i++) {

        cin>>m;
        string s1,s2;
        int temp=0;
        flag=1;
        zero(visited);
        map<string , int>mp;
        for(int k=0; k<m; k++) {
            cin>>s1>>s2;
            if(mp.find(s1)==mp.end())mp[s1]= ++temp;
            if(mp.find(s2)==mp.end())mp[s2]= ++temp;
            int p = mp[s1],q=mp[s2];
            G[p].pb(q);
        }
        for(int k=1; k<=temp; k++) {
            if(!visited[k]) {
                if(dfs(k,visited,backedge)) {
                    flag=0;
                    break;
                }
            }
        }
        if(flag)printf("Case %d: Yes\n",i);
        else printf("Case %d: No\n",i);
        rep( i , 10000+2 )G[i].clear() ;
    }
    return 0 ;
}