如题,不懂为啥要建反向图,我直接按tarjan出来的拓扑序在原图dfs就AC了,我错了吗?
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e3+5;
const int INF = 0x3fffffff;
const int mod = 100003;
#define lp(i,l,r) for(register int i=(l);i<=(r);++i)
#define rp(i,r,l) for(register int i=(r);i>=(l);--i)
vector<int> e[MAXN];
vector<int> ec[MAXN];
int dfn[MAXN], low[MAXN], scc[MAXN], cscc, cnt;
long long siz[MAXN];
bool ins[MAXN];
stack<int> stk;
void tarjan(int p)
{
dfn[p] = low[p] = ++cnt;
stk.push(p);
ins[p] = 1;
for(auto&q:e[p]) {
if(!dfn[q]) {
tarjan(q);
low[p] = min(low[p], low[q]);
}
else if(ins[q]) {
low[p] = min(low[p], dfn[q]);
}
}
if(low[p] == dfn[p]) {
int top;
cscc++;
do {
top = stk.top();
stk.pop();
ins[top] = 0;
scc[top] = cscc;
siz[cscc]++;
} while(top != p);
}
}
bitset<MAXN> f[MAXN];
bool vis[MAXN];
void dfs(int p)
{
vis[p] = 1;
f[p][p] = 1;
for(auto&q:ec[p]) {
if(!vis[q]) {
vis[q] = 1;
dfs(q);
}
f[p] |= f[q];
}
}
void solve()
{
int n;
cin >> n;
lp(i,1,n)
lp(j,1,n) {
char m;
cin >> m;
if(m == '1')
e[i].push_back(j);
}
lp(i,1,n)
if(!dfn[i])
tarjan(i);
lp(u,1,n) {
for(auto&v:e[u]) {
if(scc[u] != scc[v]) {
ec[scc[u]].push_back(scc[v]);
}
}
}
rp(i,cscc,1) {
if(!vis[i]) {
dfs(i);
}
}
long long ans = 0;
lp(i,1,cscc) {
lp(j,1,cscc) {
if(f[i][j]) {
ans += siz[i] * siz[j];
}
}
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin>>T;
while(T--)solve();
}