记录

dalao 们求条

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;

int n, t, head, ta;
int dfn[N], low[N], st[N], bel[N], cnt[N], deg[N];
bool instk[N];
char mp[N][N];
vector<int> tr[N], tr2[N];
bitset<N> f[N];

void tarjan(int u)
{
	low[u] = dfn[u] = ++t;
	instk[u] = 1;
	st[++head] = u;
	for (int v : tr[u])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (instk[u])
			low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u])
	{
		int x;
		ta++;
		while (1)
		{
			x = st[head--]; 
			bel[x] = ta;
			cnt[ta]++;
			instk[x] = 0;
			if (x == u) break;
		}
		f[ta][ta] = 1;
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%s", mp[i] + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (mp[i][j] == '1') tr[i].push_back(j);
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; i++)
	{
		for (int j : tr[i])
		{
			if (bel[i] == bel[j]) continue;
			tr2[bel[j]].push_back(bel[i]);
			deg[bel[i]]++;
		}
	}
	queue<int> q;
	for (int i = 1; i <= ta; i++)
		if (!deg[i]) q.push(i);
	while (q.size())
	{
		int u = q.front();
		q.pop();
		for (int v : tr2[u])
		{
			deg[v]--;
			f[v] |= f[u];
			if (!deg[v]) q.push(v);
		}
	}
	int ans = 0;
	for (int i = 1; i <= ta; i++)
		for (int j = 1; j <= ta; j++)
			if (f[i][j]) ans += cnt[i] * cnt[j];
	printf("%d\n", ans);
	return 0;
}