FilesExpand file tree

 master

/

11060.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

86 lines (72 loc) · 1.45 KB

 master

/

11060.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

86 lines (72 loc) · 1.45 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

#include <iostream>

#include <map>

#include <vector>

#include <string.h>

#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

vector < pii > stamp;

map<string, int> mymap;

int N,M;

const int MAXN = 240;

int g[MAXN][MAXN];

int global_t;

int test_case = 0;

string alco[MAXN];

bool vis[MAXN];

void dfs(int cur){

if(vis[cur])return ;

vis[cur]=1;

global_t++;

for(int i=0; i<N; i++){

if(g[cur][i]){

dfs(i);

}

}

global_t++;

stamp.push_back( pii(global_t, cur));

}

void work(){

global_t = 0;

memset(vis,0,sizeof(vis));

for(int i=0; i<N; i++){

dfs( mymap[alco[i]]);

}

sort(stamp.rbegin(), stamp.rend());

cout<<"Case #"<<test_case<<": Dilbert should drink beverages in this order:";

for(int i=0; i<N; i++){

cout<<" "<<alco[stamp[i].second];

}

cout<<"."<<endl;

}

void init(){

memset(vis,0,sizeof(vis));

memset(g,0,sizeof(g));

stamp.clear();

}

int main(){

int blank = 0;

while(cin>>N){

init();

mymap.clear();

if(blank!=0){

cout<<endl;

}

test_case++;

blank++;

string s;

string s1,s2;

for(int i=0; i<N; i++){

cin>>s;

alco[i] = s;

mymap[s] = i;

}

cin>>M;

for(int i=0; i<M; i++){

cin>>s1>>s2;

g[mymap[s1]][mymap[s2]] = 1;

}

work();

}

return 0;

}