FilesExpand file tree

 master

/

1129.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

82 lines (71 loc) · 1.33 KB

 master

/

1129.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

82 lines (71 loc) · 1.33 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

#include <iostream>

using namespace std;

int N;

int g[30][30];

int vis[30];

int t_v[30];

int ans = -1;

void dfs(int node){

if(vis[node]!=0){

return ;

}

//cout<<node<<endl;

memset(t_v,0,sizeof(t_v));

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

if(g[node][j] && vis[j]>0){

t_v[vis[j]] = 1;

}

}

int p = -1;

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

if(t_v[i]==0){

p = i;

break;

}

}

vis[node] = p;

if(p>ans){

ans = p;

}

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

if(g[node][j]){

dfs(j);

}

}

}

void work(){

ans = -1;

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

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

dfs(i);

}

if(ans<=1){

cout<<ans<<" channel needed."<<endl;

}else{

cout<<ans<<" channels needed."<<endl;

}

}

int main(){

while(1){

scanf("%d",&N);

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

if(N==0)break;

char s;

char adj[30];

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

scanf("%s",adj);

for(int j=2; j<strlen(adj); j++){

g[i][adj[j]-'A'] = 1;

}

}

/*

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

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

cout<<g[i][j]<<" ";

}cout<<endl;

}

*/

work();

}

return 0;

}