标签：tarjan，bitset，拓扑排序
Description
Input
输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
Output
输出一行一个整数，表示该图的连通数。
Sample Input
3
010
001
100
Sample Output
9
HINT
对于100%的数据，N不超过2000。
分析：
Tarjan缩点重新构图
F[i][j]表示i和j点之间的联通情况，然后按照拓扑序从后往前整体取或，最后用每个联通块的大小来更新答案
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2006;
int n,cnt=0,scc,top=0,tim,lim,ans=0;
int head[maxn],h[maxn],r[maxn],dfn[maxn],low[maxn],que[maxn],inque[maxn];
int belong[maxn],hav[maxn],mark[maxn][maxn];
char ch[maxn];
struct edge{int to,next;}e[4000006],ed[4000006];
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define v e[i].to
#define newreg(x) for(int i=h[x];i;i=ed[i].next)
#define newv ed[i].to
void tarjan(int x)
{
int now=0;
dfn[x]=low[x]=++tim;que[++top]=x;inque[x]=1;
reg(x)
if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}
else if(inque[v])low[x]=min(low[x],dfn[v]);
if(low[x]==dfn[x]){
scc++;
while(now!=x){
now=que[top--];
inque[now]=0;belong[now]=scc;hav[scc]++;
}
}
}
void rebuild()
{
cnt=0;
rep(k,1,n)
reg(k)
if(belong[k]!=belong[v])ed[++cnt]=(edge){belong[k],h[belong[v]]},h[belong[v]]=cnt,r[belong[k]]++;
}
int main()
{
n=read();
lim=n/30+1;
rep(i,1,n){
scanf("%s",ch);
rep(j,1,n)
if(ch[j-1]-'0')e[++cnt]=(edge){j,head[i]},head[i]=cnt;
}
rep(i,1,n)
if(!dfn[i])tarjan(i);
rebuild();
top=0;int now;
rep(i,1,n)mark[belong[i]][i/30+1]|=(1<<(i%30));
rep(i,1,scc)if(!r[i])que[++top]=i;
while(top){
now=que[top--];
newreg(now){
rep(j,1,lim)mark[newv][j]|=mark[now][j];
r[newv]--;
if(!r[newv])que[++top]=newv;
}
}
rep(i,1,scc)
rep(j,1,n)
if((mark[i][j/30+1])&(1<<(j%30)))ans+=hav[i];
cout<<ans<<endl;
return 0;
}
