BZOJ_2208_[Jsoi2010]连通数_强连通分量+拓扑排序+手写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。
直接缩点+拓扑排序统计答案即可。
每步转移是O(n)的，可以用bitset优化到O(n/32)。
其实就是想练习一下手写bitset，显然没有STL的块。
总时间复杂度O(nnm/32)
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2050
#define M 4000500
#define _min(x,y) ((x)<(y)?(x):(y))
typedef unsigned int ut;
const int M1=65535;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rc() {
char s=nc();
while(s<'0'||s>'1') s=nc();
return s=='1';
}
int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
int n,block,h[1<<16];
int g1(unsigned int x) {
return h[x>>16]+h[x&M1];
}
struct Bitset {
ut b[70];
int get_num() {
int i,re=0;
for(i=1;i<=block;i++) re+=g1(b[i]);
return re;
}
Bitset operator | (const Bitset &x) const {
Bitset re; int i;
for(i=1;i<=block;i++) re.b[i]=(b[i]|x.b[i]);
return re;
}
}f1[N],f2[N];
int head[N],to[M],nxt[M],in[N],Q[N],l,r;
int S[N],bel[N],siz[N],L[80],R[80],pos1[N],pos2[N],dfn[N],low[N],tot,scc,top,ins[N],xx[M],yy[M],qwq,cnt;
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void dfs(int x) {
int i;
dfn[x]=low[x]=++tot; S[++top]=x; ins[x]=1;
for(i=head[x];i;i=nxt[i]) {
if(!dfn[to[i]]) {
dfs(to[i]);
low[x]=_min(low[x],low[to[i]]);
}else if(ins[to[i]]) {
low[x]=_min(low[x],dfn[to[i]]);
}
}
if(dfn[x]==low[x]) {
int t=S[top--]; ins[t]=0;
bel[t]=++scc; f2[scc]=f1[t];
siz[scc]=1;
while(t!=x) {
t=S[top--]; ins[t]=0;
bel[t]=scc; f2[scc]=f2[scc]|f1[t];
siz[scc]++;
}
}
}
int main() {
n=rd();
register int i,j;
int x;
for(i=1;i<=M1;i++) h[i]=h[i>>1]+(i&1);
block=n/32;
for(i=1;i<=block;i++) {
L[i]=R[i-1]+1; R[i]=i*32;
for(j=L[i];j<=R[i];j++) {
pos1[j]=i; pos2[j]=j-L[i];
}
}
if(R[block]!=n) {
L[block+1]=R[block]+1; R[++block]=n;
for(i=L[block];i<=n;i++) pos1[i]=block,pos2[i]=i-L[block];
}
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
x=rc();
if(x) f1[i].b[pos1[j]]|=(1<<pos2[j]),add(i,j),xx[++qwq]=j,yy[qwq]=i;
}
f1[i].b[pos1[i]]|=(1<<pos2[i]);
}
for(i=1;i<=n;i++) {
if(!dfn[i]) dfs(i);
}
memset(head,0,sizeof(head)); cnt=0;
for(i=1;i<=qwq;i++) {
if(bel[xx[i]]!=bel[yy[i]]) {
add(bel[xx[i]],bel[yy[i]]); in[bel[yy[i]]]++;
}
}
for(i=1;i<=scc;i++) {
if(!in[i]) Q[r++]=i;
}
int ans=0;
while(l<r) {
x=Q[l++]; ans+=siz[x]*f2[x].get_num();
for(i=head[x];i;i=nxt[i]) {
in[to[i]]--;
f2[to[i]]=f2[to[i]]|f2[x];
if(in[to[i]]==0) Q[r++]=to[i];
}
}
printf("%d\n",ans);
}
