CF402E Strictly Positive Matrix 题解 tarjan强连通分量

题目链接：http://codeforces.com/problemset/problem/402/E

题目大意：

给出一个矩阵 \(A\)，问是否存在一个正整数 \(k\) 使得 \(A^k\)

解题思路：

根据矩阵的性质，\(A^k_{i,j} \gt 0\) 当且仅当 \(i\) 到 \(j\)

所以可以把矩阵转成图论模型，若 \(A_{i,j} \gt 0\)，则从 \(i\) 往 \(j\)

如果所有点处在同一个强连通分量，则为 "YES"；否则，为 "NO"。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int n, a, dfn[maxn], low[maxn], id[maxn], ts, scc;
bool ins[maxn];
vector<int> g[maxn];
stack<int> stk;

void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk.push(u), ins[u] = true;
    for (auto v : g[u]) {
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        int v;
        do {
            v = stk.top(); stk.pop();
            ins[v] = false;
            id[v] = scc;
        } while (v != u);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a);
            if (a && i != j) g[i].push_back(j);
        }
    }
    tarjan(1);
    for (int i = 1; i <= n; i++) {
        if (id[i] != 1) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;
}