Description

Input

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

Output

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

Sample Input

3 

010 

001 

100

Sample Output

9

HINT

 

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

 

Source

Solution

好好的暴力不写去写什么算法

虽然我也是学算法学傻了的，前两天看到一道题说这不是莫队裸题吗，然后其实前缀和就行了

做法1：$tarjan$缩点+拓扑

做法2：$floyd$传递闭包

做法3：暴力$dfs$

因为我这人比较菜所以就写做法3了

对于每个点直接开一个$vis$数组判断有没有到达过就可以了

比tarjan短多了

#include 
     
      using namespace std ;#define N 2010#define ll long long int n , head[ N ] , cnt , vis[ N ] ;  struct node {    int to , nxt ;}e[ N * N ] ;void ins( int u , int v ) {    e[ ++ cnt ].to = v ;    e[ cnt ].nxt = head[ u ] ;     head[ u ] = cnt ; }ll find( int u ) {    ll ans = 1 ;    vis[ u ] = 1 ;    for( int i = head[ u ] ; i ; i = e[ i ].nxt ) {        if( vis[ e[ i ].to ] ) continue ;        ans += find( e[ i ].to ) ;    }    return ans ;}int main() {    scanf( "%d" , &n ) ;    for( int i = 1 ; i <= n ; i ++ ) {        char ch[ 2010 ] ;        scanf( "%s" , ch + 1 ) ;        for( int j = 1 ; j <= n ; j ++ ) {            if( ch[ j ] == '1' ) {                ins( i , j ) ;             }        }    }    ll ans = 0 ;    for( int i = 1 ; i <= n ; i ++ ) {        memset( vis , 0 ,sizeof( vis ) ) ;        ans += find( i ) ;//        printf( "Case #%d : %d\n" , i , ans - t ) ;    }    printf( "%lld\n" , ans ) ;    return 0 ;}