提交记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 2010;

int n, g[N][N], graph[N][N], in[N];
vector<int> e[N];
int dfn[N], low[N], scc[N], sz[N], stk[N], instk[N], tot, top, cnt;
ll f[N];

int gc() {
	int x = getchar();
	if (x != '0' && x != '1') return gc();
	else return x;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    instk[u] = 1;
    for (int i = 1; i <= n; i++) {
        if (g[u][i]) {
            if (!dfn[i]) {
                tarjan(i);
                low[u] = min(low[u], low[i]);
            } else if (instk[i]) {
                low[u] = min(low[u], dfn[i]);
            }
        }
    }
    if (dfn[u] == low[u]) {
        int y;
        cnt++;
        do{
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            sz[cnt]++;
        }while(y != u);
    }
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= cnt; i++) {
        f[i] = sz[i];
        if (!in[i]) q.push(i);
    }
    while(q.size()) {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= cnt; i++) {
            if (graph[t][i]) {
                f[i] += f[t];
                in[i]--;
                if (!in[i]) q.push(i);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char c; c = gc();
            if (c == '1') g[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j]) {
                //i->j
                graph[scc[j]][scc[i]] = 1;
                //e[scc[j]].push_back(scc[i]);
                in[scc[i]]++;
            }
        }
    }
    topsort();
    ll ans = 0;
    for (int i = 1; i <= cnt; i++) ans += f[i] * sz[i];
    printf("%lld\n", ans);
    return 0;
}