Description:


Input:


输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。

Output:


输出一行一个整数,表示该图的连通数。

Sample Input:


Sample Output:


HINT:


对于100%的数据,N不超过2000。

题解:


这个题不知道时限是多少,用 \(O(m\times n)\) 的算法可以过……
我们对原图求强连通分量缩点,然后每一个点去DFS一遍求出可以到达的点。
理论上来说DAG图的边数可能达到 \(n^2\) 的级别,那么这个算法是可以被卡掉的。
然而它就是过了。