简单来讲就是 BFS 会 T 啦

Problem

https://lydsy.com/JudgeOnline/problem.php?id=2208

Solution

luogu 数据有毒
后面几乎瞎几把写了能有 90 分..

BFS 是 $O(NM)$ 的... 所以要冷静啊不能一上来就暴力呀...（虽然我并没有打）

然后如果是拓扑序的话就可以 bitset 乱搞啦

所以缩点愉快搞一下就行啦

Code

// Code by ajcxsu
// Problem: connection

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

const int N=2010, M=N*N*4;
int h[N], h2[N], to[M], nexp[M], p=1;
int in[N];
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
inline void ins2(int a, int b) { nexp[p]=h2[a], h2[a]=p, to[p]=b, p++, in[b]++; }

typedef bitset<N> bs;
bs con[N];

int dfn[N], siz[N], low[N], stk[N], scc[N], sidx, idx, t;
char instk[N];
void tarjan(int x) {
    dfn[x]=low[x]=++idx, stk[++t]=x, instk[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) tarjan(to[u]), low[x]=min(low[x], low[to[u]]);
        else if(instk[to[u]]) low[x]=min(low[x], dfn[to[u]]);
    if(low[x]==dfn[x]) {
        sidx++;
        do {
            scc[stk[t]]=sidx, instk[stk[t]]=0;
            siz[sidx]++;
        } while(stk[t--]!=x);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    char ch;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) {
        cin>>ch;
        if(ch=='1') ins(i, j);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        for(int u=h[i];u;u=nexp[u])
            if(scc[to[u]]!=scc[i]) ins2(scc[to[u]], scc[i]);
    queue<int> qu;
    for(int i=1;i<=sidx;i++) {
        con[i][i]=1;
        if(!in[i]) qu.push(i);
    }
    int na;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int u=h2[na];u;u=nexp[u]) {
            con[to[u]]|=con[na];
            if(!(--in[to[u]])) qu.push(to[u]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(con[scc[i]][scc[j]]) ans++;
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-bzoj-2208.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆