RT,缩点+拓扑排序,不知道哪里错了
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define Withers using
#define AK namespace
#define IOI std;
#define ACM __gnu_pbds
Withers AK IOI;
Withers AK ACM;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,u,v,w,x,y,z,t,l,r,minn=INT_MAX,maxx=INT_MIN,len,res,pos,id,as,k;
int a[200010];
string s;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define endl '\n'
#define rd read
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
#define deb(x) cout<<#x<<"="<<x<<" ";
vector<int> g1[200010],g[200010];
int cnt1,cnt2;
bool vis1[100010],vis2[200010];
int st[100010];
int from[100010];
bool vis[100010];
int sum=0;
void dfs(int u)
{
if(vis1[u]) return;
vis1[u]=1;
//cout<<u<<endl;
for(auto i:g[u])
{
if(vis1[i]) continue;
dfs(i);
}
st[++cnt1]=u;
}
void dfs2(int u)
{
//cout<<u<<"nmsl\n\n";
if(vis2[u]) return;
vis2[u]=1;
sum+=1;
from[u]=cnt2;
//cout<<u<<" "<<cnt2<<endl;
for(auto i:g1[u])
{
//cout<<i<<" "<<u<<"qwq\n";
if(vis2[i]) continue;
dfs2(i);
//cout<<i<<" "<<u<<"qwq\n";
}
}
int siz[100010];//dp[100010];
vector<int> f[100010];
int in[100010];
//bool add[2010][2010];
bitset<2010> dp[2010];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;//rd(m);
// for(int i=1;i<=n;i++) rd(a[i]);
// for(int i=1;i<=m;i++)
// {
// // rd(u);rd(v);
// // g[u].push_back(v);
// // g1[v].push_back(u);
// }
for(int i=1;i<=n;i++)
{
cin>>s;
//cout<<s<<endl;
for(int j=0;j<n;j++)
{
if(s[j]=='1') g[i].push_back(j+1),g1[j+1].push_back(i);
}
}
for(int i=1;i<=n;i++)
{
if(!vis1[i]) dfs(i);
}
for(int i=n;i>=1;i--)
{
//cout<<st[i]<<"awa\n";
if(!vis2[st[i]])
{
cnt2++;
sum=0;
dfs2(st[i]);
siz[cnt2]=sum;
}
}
//cout<<cnt1<<" "<<cnt2<<'\n';
for(int i=1;i<=n;i++)
{
for(auto j:g[i])
{
if(from[i]!=from[j]&&!dp[from[i]][from[j]])
{
f[from[i]].push_back(from[j]);
dp[from[i]][from[j]]=1;
in[from[j]]++;
//cout<<from[i]<<" "<<from[j]<<endl;
}
}
}
ll sum=0;
for(int i=1;i<=cnt2;i++) dp[i][i]=1;
memset(vis,0,sizeof(vis));
queue<int> q;
for(int i=1;i<=cnt2;i++) if(!in[i]) q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
for(auto i:f[u])
{
dp[i]|=dp[u];
if(!(--in[i])) q.push(i);
}
}
for(int i=1;i<=cnt2;i++)
{
for(int j=1;j<=cnt2;j++)
{
//cout<<add[i][j]<<'\n';
if(dp[i][j]) sum+=1ll*siz[i]*siz[j];
}
}
cout<<sum;
}
// POWERED BY WITHERS
// THINK ONCE, CODE TWICE