codeforce 402 E(マトリクス&強連通)

タイトル:http://codeforces.com/problemset/problem/402/E
負の数のない行列K乗を求めると、すべての要素が正数であるかどうかがわかります.
分析:
マトリックスグラフィックス.  正为1:道がある;  0は0:パスなし.a^k後、a[i][j]が正であれば、i点からちょうどk歩でj点まで行ける道があることを説明します.初期化マトリクスの要素は1または0であり、K乗後マトリクスの要素には0または正の整数の2つの結果しかありません.t 1べき乗後の要素aの値が正の整数である場合、t 1+1べき乗後の値も正の整数である.従って、kが無限大になると、問題は、元のマトリクスが表す図が強い連通であるかどうかを尋ねることに変換される.

    ：http://blog.csdn.net/thearcticocean/article/details/48056855
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e3+10;
int gra[N][N];
int sta[N],vis[N],low[N],dfn[N],top; 
void tarbfs(int k,int cnt,int &num,int n){
    vis[k]=1;
    low[k]=cnt;
    dfn[k]=cnt;
    sta[top++]=k;
    for(int j=n;j>0;j--){  //k
        if(gra[k][j]>0&&vis[j]==0) tarbfs(j,++cnt,num,n);
        if(gra[k][j]>0&&vis[j]==1) low[k]=min(low[k],low[j]);
    }
    if(dfn[k]==low[k]){
        ++num;
        while(top>0&&sta[top]!=k){
            top--;
            low[sta[top]]=num;
            vis[sta[top]]=2;
        }
    }
}
int tarjan(int n){
    int num=0,cnt=1;
    top=0;
    memset(vis,0,sizeof(vis));
    memset(low,0,sizeof(low));
    for(int i=1;i<=n;i++){
        if(vis[i]==0) tarbfs(i,cnt,num,n);
    }
    return num;
}

int main()
{
    //freopen("cin.txt","r",stdin);
    int n,a;
    while(cin>>n){
        memset(gra,0,sizeof(gra));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a);
                if(a>0) gra[i][j]=1;
            }
        }
        int num=tarjan(n);
        if(num==1) puts("YES");
        else puts("NO");
    }
    return 0;
}