ligjt oj---1003 - Drunk

1. #include <algorithm>
2. #include <cassert>
3. #include <cctype>
4. #include <cfloat>
5. #include <climits>
6. #include <cmath>
7. #include <cstdio>
8. #include <cstdlib>
9. #include <cstring>
10. #include <iostream>
11. #include <limits>
12. #include <map>
13. #include <queue>
14. #include <set>
15. #include <sstream>
16. #include <stack>
17. #include <string>
18. #include <utility>
19. #include <vector>
20. #define G getchar()
21. #define FOR(i,t) for(i=1;i<=t;i++)
22. #define FORO(j,n) for(j=0;j<n;j++)
23. #define EPS DBL_EPSILON
24. #define abs(x) (((x)<0)?-(x):(x))
25. #define ZERO(x) (abs(x) < EPS)
26. #define EQ(a,b) (ZERO((a)-(b)))
27. #define max(a,b) (a)>(b)?(a):(b)
28. #define min(a,b) (a)<(b)?(a):(b)
29. #define memo(a,v) memset(a,v,sizeof(a))
30. #define PI 2*acos(0.0)
31. #define all(a) a.begin(),a.end()
32. #define EPS 1e-8
33. #define INF -1U >> 1
34. #define LL int int
35. #define NL puts("")
36. #define MAX 30001
37. using namespace std;
38. map<string ,int >m;
39. vector<int >v[20010];
40. //string st1,st2;
41. char in[20010];
42. int j=0;
43. void fix(int i)
44. {
45.     int k;
46.     in[i]=-1;
47.     FORO(k,v[i].size())
48.            {
49.                in[v[i][k]]--;
50.            }
51. }
53. bool comp(int a,int b)
54.  {
55.      if(a>b) return true;
56.      return false;
57.  }
59. int main()
60.  {
61.      int i,t;
62.      scanf("%d",&t);
64.      FOR(i,t)
65.       {
66.           m.clear();
67.           memo(in,0);
69.          int a,k;
70.          j=0;
71.           scanf("%d",&a);
72.           while(a--)
73.            {
74.                G;
75.                char st1[100],st2[100];
76.                scanf("%s %s",&st1,&st2);
77.                if(!(m.count(st1)>0))
78.                 m[st1]=j++;
79.                if(!(m.count(st2)>0))
80.                 m[st2]=j++;
81.                v[m[st1]].push_back(m[st2]);
82.                in[m[st2]]++;
83.            }
84.           int fin;
85.          fin = 0;
87.          while(fin<j)
88.           {
89.             FORO(k,j)
90.              if(in[k]==0)
91.                   fix(k);
92.             fin++;
93.           }
94.          //FORO(k,j) printf("%d ",in[k]);
95.          //NL;
96.          sort(in,in+j,comp);
98.          if(in[1]>0)
99.           printf("Case %d: No\n",i);
100.          else printf("Case %d: Yes\n",i);
101.        FORO(k,j)
102.         v[k].clear();
104.       }
105.       return 0;
106.  }