【BZOJ2208】[JSOI2010]联通数（Tarjan）
题面
题解
先吐槽辣鸡洛谷数据，我写了个\(O(nm)\)的都过了。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 2020
struct Line{int v,next;}e[MAX*MAX];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int vis[MAX],ans,dep,n;char g[MAX];
void dfs(int u)
{
if(vis[u]==dep)return;
vis[u]=dep;++ans;
for(int i=h[u];i;i=e[i].next)dfs(e[i].v);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",g+1);
for(int j=1;j<=n;++j)
if(g[j]=='1')Add(i,j);
}
for(int i=1;i<=n;++i)dep=i,dfs(i);
printf("%d\n",ans);
}正经点。
这玩意既然是有向图，直接给他缩了就变\(DAG\)了，似乎直接\(dp\)一下就好了？
然而直接\(dp\)没法维护哪些点走过了，所以咱来\(bitset\)一下就好了？
#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
#define MAX 2020
struct Line{int v,next;}e[MAX*MAX];
int h[MAX],cnt=1,dg[MAX];
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int n;char g[MAX];
bool ins[MAX];
int dfn[MAX],low[MAX],St[MAX],top,gr,G[MAX],tim,sz[MAX];
bitset<2020> s[MAX];
vector<int> E[MAX];
void Tarjan(int u)
{
dfn[u]=low[u]=++tim;ins[u]=true;St[++top]=u;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dfn[v])Tarjan(v),low[u]=min(low[u],low[v]);
else if(ins[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
int v;++gr;
do{v=St[top--];ins[v]=false;G[v]=gr;s[gr].set(v);++sz[gr];}while(u!=v);
}
}
int p[MAX],tot,ans;
void Topsort()
{
queue<int> Q;
for(int i=1;i<=gr;++i)if(!dg[i])Q.push(i);
while(!Q.empty())
{
int u=Q.front();p[++tot]=u;Q.pop();
for(int i=0,l=E[u].size();i<l;++i)
if(!--dg[E[u][i]])Q.push(E[u][i]);
}
for(int i=tot;i;--i)
for(int j=0,l=E[p[i]].size();j<l;++j)
s[p[i]]|=s[E[p[i]][j]];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",g+1);
for(int j=1;j<=n;++j)
if(g[j]=='1')Add(i,j);
}
for(int i=1;i<=n;++i)if(!dfn[i])Tarjan(i);
for(int u=1;u<=n;++u)
for(int i=h[u];i;i=e[i].next)
if(G[u]!=G[e[i].v])
E[G[u]].push_back(G[e[i].v]),++dg[G[e[i].v]];
Topsort();
for(int i=1;i<=gr;++i)ans+=s[i].count()*sz[i];
printf("%d\n",ans);
}