Changing is a boy
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 34
Solved: 22
- Description
- Changing is a boy.He is numbered 0.There is n girls in his class.They are numbered from 1 to n.
Here are 3 rules:
1:
If person1 knows person2’s phone number,then we mean person1 can get direct link with person2.
2:
If person1 knows person2’s phone number,and person2 knows person3’s phone number,then we mean person1 can get indirect link with person3.
3:
If person1 can get indirct link with person2,and person2 can get indirct link with person3,then person1 can get indirct link with person3.
Changing wants to BG the girls in his class,and he will BG those girls he can get direct link or indirct link with.
He want’s to know how many girls he will BG.
(BG in here means invite the girl(or girls) to dinner) - Input
- First line an integer T,the number of test cases;
At the first line of each case one integer n(1<=n<=4) , the number of girls in Changing’s class.
Next will be n+1 lines,each line with n+1 integers.
If the j’s number in the i’s line is 1,it means personi can get direct link with personj,otherwise if that number is 0,it means personi can’t get direct link with personj.
If person1 knows person2’s phone number,then person2 will also knows person1’s phone number.
There will be an empty line after each case. - Output
- For each case,print exact one integer the number of girls Changing can get dirct or indirct link with in one line.
- sample input
-
4 2 1 1 1 1 1 1 1 1 1 1 1 0 0 1 2 1 0 1 0 1 0 1 0 1 3 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1
- sample output
-
2 0 1 3 HINT You can use floyd algorithm to solve this problem. It's format are like this: For（int k=1;k<=n;k++） For(int i=1;i<=n;i++) For(int j=1;j<=n;j++) { ……………; } - hint
- source
- Dongxu Li