subtask210分求条

#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

vector<int> g[2005];
set<int> dag[2005];
int n;
long long ans, f[2005];
char ch;
stack<int> s;
int low[2005], dfn[2005], dfncnt, scc[2005], id;
long long scc_size[2005];
bool in_stack[2005];
int indegree[2005];

void tarjan(int u)
{
    low[u] = dfn[u] = ++dfncnt;
    s.push(u);
    in_stack[u] = true;
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++id;
        while (true) {
            int top = s.top();
            s.pop();
            in_stack[top] = false;
            scc[top] = id;
            scc_size[id]++;
            if (top == u)
                break;
        }
    }
}

void build_dag()
{
    for (int u = 1; u <= n; u++)
        for (int v : g[u])
            if (scc[v] != scc[u]) {
                indegree[scc[v]]++;
                dag[scc[u]].insert(scc[v]);
            }
}

int dfs(int u)
{
    if (f[u])
        return f[u];
    f[u] = scc_size[u];
    for (int v : dag[u])
        f[u] += dfs(v);
    ans += f[u] * scc_size[u];
    return f[u];
}

void calculate_reach()
{
    for (int i = 1; i <= id; i++)
        if (indegree[i] == 0) {
            dfs(i);
        }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> ch;
            if (ch == '1')
                g[i].push_back(j);
        }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    build_dag();
    calculate_reach();
    cout << ans << endl;
    return 0;
}