妹子刚学OI性感Tarjian在线求优化

#include<iostream>
#include<queue>
#include<bitset>
#include<cstring>
#include<map>
using namespace std;
struct Edge{
    int l,nxt;
}edges[5000005],ed[5000005];
string s;
int n,m,tt=1,ttt=1,head[2005],h[2005];
int ans,du[2005],vu[2005];
int tot,dfn[2005],low[2005];
int top,stk[2005],instk[2005];
int cnt,scc[2005],scs[2005];
map<pair<int,int>,int> mo;
queue<int> qo;
bitset<20005> anu[2005];
void add_edge(int f,int l){
    tt+=1;
    edges[tt]={l,head[f]};
    head[f]=tt;
}
void add1(int f,int l){
    ttt+=1;
    ed[ttt]={l,h[f]};
    h[f]=ttt;
}
void tarjian(int x){
    tot+=1,top+=1;
    dfn[x]=low[x]=tot;
    instk[x]=1,stk[top]=x;
    for(int i=head[x];i;i=edges[i].nxt){
        int l=edges[i].l;
        if(!low[l]){
            tarjian(l);
            low[x]=min(low[x],low[l]);
        }
        else if(instk[l]) low[x]=min(low[x],dfn[l]);
    }
    if(low[x]==dfn[x]){
        int y;cnt+=1;
        do{
            y=stk[top],top-=1,instk[y]=0;
            scc[y]=cnt,scs[cnt]+=1;
        }while(y!=x);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
         for(int j=0;j<s.size();j++){
            if(s[j]=='1'){
                add_edge(i,j+1);
            }
        }
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjian(i);
    for(int f=1;f<=n;f++){
        for(int i=head[f];i;i=edges[i].nxt){
            int l=edges[i].l;
            if(scc[f]==scc[l]||mo[{scc[f],scc[l]}]) continue;
            mo[{scc[f],scc[l]}]=1;
            add1(scc[l],scc[f]);
            du[scc[f]]+=1;//从后更新前
        }
    }
    for(int i=1;i<=cnt;i++){
        if(!du[i]) qo.push(i);
        anu[i][i]=1;
    }
    while(!qo.empty()){
        int x=qo.front();qo.pop();
        for(int i=h[x];i;i=ed[i].nxt){
            int l=ed[i].l;
            anu[l]|=anu[x];
            du[l]-=1;
            if(!du[l]) qo.push(l);
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            if(anu[i][j]==1) ans+=scs[i]*scs[j];
        }
    }
    cout<<ans;
    return 0;
}