看了题解的用h[i][j]表示强连通分量i和j的写法,但是不知道自己的方法错哪 orz
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x & -x
#define int long long
#define pii pair<int ,int >
#define fi first
#define se second
#define ull unsigned long long
#define find1(x) __builtin_popcount(x)
const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7;
const long long INF=0x3f3f3f3f3f3f3f3f;
mt19937_64 rnd(random_device{}());
uniform_int_distribution<ull> dist(0, ULLONG_MAX); // use dist(rnd)
int dfn[N] , scc[N] , low[N], stk[N] , V[N];
int tot = 0 , scc_cnt = 0 , top;
vector<int > edge[N] , E[N];
int In[N];
int dp[N];
void Tarjan(int u)
{
dfn[u] = low[u] = ++tot;
stk[++top] = u;
for(auto v : edge[u])
{
if(!dfn[v])
{
Tarjan(v);
low[u] = min(low[u] , low[v]);
}
else if(!scc[v])
{
low[u] = min(low[u] , dfn[v]);
}
}
if(dfn[u] == low[u])
{
int x;
scc_cnt ++;
do
{
x = stk[top--];
scc[x] = scc_cnt;
V[scc_cnt] ++;
}while(x != u);
}
}
int Ans ;
void solve() {
int n ;
cin >> n ;
for(int i = 1 ; i <= n; i ++)
{
string s ;
cin >> s;
s = ' ' + s;
for(int j = 1 ; j <= n ; j ++)
{
if(j == i) continue;
if(s[j] == '1')
{
edge[i].push_back(j);
}
}
}
for(int i = 1 ; i <= n ; i ++)
{
if(!dfn[i]) Tarjan(i);
}
int root = 0 ;
for(int i = 1 ; i <= n ; i ++)
{
for(auto v : edge[i])
{
int u = scc[i];
v = scc[v];
if(u != v)
{
E[v].push_back(u);
In[u] ++;
}
}
}
queue<int > q ;
for(int i = 1 ; i <= scc_cnt ; i ++)
{
if(!In[i]) q.push(i);
dp[i] = V[i];
}
while(q.size())
{
int u = q.front();
q.pop();
Ans += (dp[u]) * V[u];
// cout << "Ans = " << Ans << '\n';
for(auto v : E[u])
{
In[v] --;
dp[v] += dp[u];
if(In[v] == 0)
{
q.push(v);
}
}
}
cout << Ans << '\n';
}
#undef int
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cout<<fixed<<setprecision(15);
// int _ = 1;cin >>_;while(_--)
{
solve();
}
return 0;
}