Problem5679--朋友圈 II

5679: 朋友圈 II

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

班上有 $N$ 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 $A$ 是 $B$ 的朋友,$B$ 是 $C$ 的朋友,那么我们可以认为 $A$ 也是 $C$ 的朋友。所谓的朋友圈,是指所有朋友的集合。
给定一个 $N∗N$ 的矩阵 $M$,表示班级中学生之间的朋友关系。如果 $M[i][j]=1$,表示已知第 $i$ 个和 $j$ 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈人数最多的数目。

Input

第一行为一个整数 $N\ (1≤N≤10^4)$。
第 $2$ 到 $N+1$ 行,每行包括 $N$ 个数。每个数据不是 $0$ 就是 $1$。

Output

一行一个整数。表示所有学生中的已知的朋友圈人数最多的数量。

Sample 1 Input

3
1 1 0
1 1 0
0 0 1

Sample 1 Output

2
已知学生 $0$ 和学生 $1$ 互为朋友,他们在一个朋友圈。第 $2$ 个学生自己在一个朋友圈。人数最多的朋友圈人数为 $2$。

Sample 2 Input

3
1 1 0
1 1 1
0 1 1

Sample 2 Output

3
已知学生 $0$ 和学生 $1$ 为朋友,学生 $1$ 和学生 $2$ 为朋友,所以学生 $0$ 和学生 $2$ 也是朋友,所以他们三个在一个朋友圈,返回 $3$。

Source/Category

数据结构 2.51.并查集