TOJ 4289 Unrequited Love

Description
There are n single boys and m single girls. Each of them may love none, one or several of other people unrequitedly and one-sidedly. For the coming q days, each night some of them will come together to hold a single party. In the party, if someone loves all the others, but is not loved by anyone, then he/she is called king/queen of unrequited love.
Input
There are multiple test cases. The first line of the input is an integer T ≈ 50 indicating the number of test cases.
Each test case starts with three positive integers no more than 30000 -- n m q . Then each of the next n lines describes a boy, and each of the next m lines describes a girl. Each line consists of the name, the number of unrequitedly loved people, and the list of these people's names. Each of the last q lines describes a single party. It consists of the number of people who attend this party and their names. All people have different names whose lengths are no more than 20 . But there are no restrictions that all of them are heterosexuals.
Output
For each query, print the number of kings/queens of unrequited love, followed by their names in lexicographical order, separated by a space. Print an empty line after each test case. See sample for more details.
Sample Input

2
2 1 4
BoyA 1 GirlC
BoyB 1 GirlC
GirlC 1 BoyA
2 BoyA BoyB
2 BoyA GirlC
2 BoyB GirlC
3 BoyA BoyB GirlC
2 2 2
H 2 O S
He 0
O 1 H
S 1 H
3 H O S
4 H He O S

Sample Output

0
0
1 BoyB
0

0
0

Source
ZJCPC 2012
 
쓸 줄 몰라, 물 문제 같은 걸 보니 이렇게 어려울 줄은 몰랐어.
만약에 한 사람이 unrequited love가 존재한다면 이 결점은 입도가 없고 이 점에서 모든 점까지는 반드시 경로가 있다는 것을 나타낸다.
소의 문제 풀이 사고방식, 데이터 비교의 대용vector 수조로 그림을 만들고 이분찾기로 통로가 있는지 판단해야 한다.
 

 1 #include <stdio.h>
 2 #include <map>
 3 #include <string>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <iostream>
 7 #define MAXN 60005
 8 using namespace std;
 9 
10 vector< int > V[MAXN];
11 vector< int > VP;
12 map< string , int > M;
13 string Name[MAXN];
14 int cnt;
15 
16 void initVP(){
17     VP.clear();
18 }
19 
20 void initGraph(){
21     for(int i=0; i<MAXN; i++){
22         V[i].clear();
23     }
24 }
25 
26 void addString(string s){
27     if(M.find(s)==M.end()){
28         M[s]=cnt;
29         Name[cnt++]=s;     
30     }
31 }
32 
33 void createMap(int n){
34     char ch[21];
35     string s;
36     int c,u,v;
37     for(int i=0; i<n; i++){
38         scanf("%s" ,ch);
39         s=string(ch);    
40         addString(s);
41         u=M[s];
42         scanf("%d" ,&c);
43         for(int j=0; j<c; j++){
44             scanf("%s" ,ch);
45             s=string(ch);
46             addString(s);
47             v=M[s];    
48             V[u].push_back(v);
49         }
50         sort(V[u].begin(),V[u].end());
51     }    
52 }
53 
54 int main()
55 {
56     int c,t;
57     int n,m,q;
58     scanf("%d" ,&t);
59     while( t-- ){
60         M.clear();
61         cnt=0;
62         initGraph();
63         scanf("%d %d %d" ,&n ,&m ,&q);
64         createMap(n);
65         createMap(m);
66         while( q-- ){
67             initVP();
68             char ch[21];
69             string s;
70             scanf("%d" ,&c);
71             while( c-- ){
72                 scanf("%s" ,ch);
73                 s=string(ch);
74                 VP.push_back(M[s]);
75             }
76             int size=VP.size();
77             int i,j;
78             for(i=0; i<size; i++){
79                 for(j=0; j<size; j++){
80                     if(i==j)continue;
81                      if( !binary_search( V[VP[i]].begin() , V[VP[i]].end(), VP[j])  
82                      || binary_search( V[VP[j]].begin(), V[VP[j]].end(), VP[i]))
83                          break; 
84                 }
85                 if(j==size){
86                     printf("1 %s
",Name[VP[i]].c_str());
87                     break;
88                 }
89             }
90             if(i==size){
91                 puts("0");
92             }
93         }
94         puts("");    
95     }
96     return 0;
97 }