1003 - Drunk
PDF (English)
Statistics
Forum
Time Limit: 2 second(s)
Memory Limit: 32 MB
One of my friends is always drunk. So, sometimes I get a bit confused whether he is drunk or not. So, one day I was talking to him, about his drinks! He began to describe his way of drinking. So, let me share his ideas a bit. I am expressing in my words.
There are many kinds of drinks, which he used to take. But there are some rules; there are some drinks that have some pre requisites. Suppose if you want to take wine, you should have taken soda, water before it. That's why to get real drunk is not that easy.
Now given the name of some drinks! And the prerequisites of the drinks, you have to say that whether it's possible to get drunk or not. To get drunk, a person should take all the drinks.
Input
Input starts with an integer T (≤ 50), denoting the number of test cases.
Each case starts with an integer m (1 ≤ m ≤ 10000). Each of the next m lines will contain two names each in the format a b, denoting that you must have a before having b. The names will contain at most10 characters with no blanks.
Output
For each case, print the case number and 'Yes' or 'No', depending on whether it's possible to get drunk or not.
Sample Input
2
2
soda wine
water wine
3
soda wine
water wine
wine water
Output for Sample Input
Case 1: Yes
Case 2: No
：：学习一个新算法，总没那么容易，今天又因为一个弄错一个字母找了半天*.*!!
1: #include <iostream>
2: #include <cstdio>
3: #include <algorithm>
4: #include <cstring>
5: #include <map>
6: using namespace std;
7: const int maxn=11000;
8: int head[maxn],in[maxn];
9: bool vis[maxn];
10: int ant,cas=1,id;
11:
12: map<string,int>a;
13: struct EDGE{
14: int v, next;
15: EDGE(){}
16: EDGE(int _v, int _next){v = _v, next = _next;}
17: }e[maxn];
18: int ecnt;
19:
20: void add(int u, int v){
21: e[ecnt] = EDGE(v, head[u]);
22: head[u] = ecnt++;
23: }
24:
25: bool topo(){
26: memset(vis, 0, sizeof(vis));
27:
28: for(int t = 0; t < id; t++){
29: int u;
30: for(u = 0; u < id; u++)
31: if(!vis[u] && !in[u])
32: break;
33: if(u >= id)
34: return false;
35:
36: vis[u] = true;
37: in[u]--;
38: for(int i = head[u]; i != -1; i = e[i].next){
39: int v = e[i].v;
40: in[v]--;
41: }
42: }
43: return true;
44: }
45:
46: void solve()
47: {
48: int n;
49: ecnt=0,id=0;
50: a.clear();
51: memset(head,-1,sizeof(head));
52: memset(in,0,sizeof(in));
53: cin>>n;
54:
55: while(n--)
56: {
57: string x,y;
58: cin>>x>>y;
59:
60: if(a.find(x)==a.end()) a[x]=id++;
61: if(a.find(y)==a.end()) a[y]=id++;
62: int u=a[x],v=a[y];
63: add(u,v);
64: in[v]++;
65: }
66: if(topo())
67: cout<<"Yes"<<endl;
68: else
69: cout<<"No"<<endl;
70: }
71:
72: int main()
73: {
74: ios::sync_with_stdio(false);
75: int t, cas = 0;
76: cin>>t;
77: while(t--){
78: cout<<"Case "<< (++cas)<<": ";
79: solve();
80: }
81: return 0;
82: }