【BZOJ2208】聯通數

分析：

求傳遞閉包，有向圖，每個環内的點的連通數都一樣，是以先縮點變成 DAG，然後按照拓撲排序倒着 dp ，用bitset維護走過的點。

bitset<N>dp[N]，設 dp[i] 表示 以點 i 為起點的連通數，即走過的點

則 若存在邊 i->j 則 dp[i] | = dp[j] 。複雜度 O ( n 2 / W ) O(n^{2}/W) O(n2/W)

代碼：

#include<queue>
#include<bitset>
#include<cstdio>
#include<iostream>
using namespace std;

const int N = 2000+10;
const int M = N*N;

char str
[N];

struct node{
	int to,nxt;
}e[M],E[M];
int hd1[N],tot1,hd2[N],tot2; 

void add(node e[],int head[],int &tot,int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}

bitset<N>dp[N];

int dfn[N],low[N],dfncnt,s[N],tp;
int scc[N],sc;
int sz[N],n;    

void tarjan(int u)
{
	low[u]=dfn[u]=++dfncnt,s[++tp]=u;
	for(int i=hd1[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v])
			tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v])
		    low[u]=min(low[u],dfn[v]); 
	}
	if(dfn[u]==low[u]){
		++sc;
		while(s[tp]!=u) dp[sc].set(s[tp]),scc[s[tp]]=sc,sz[sc]++,--tp;
		dp[sc].set(s[tp]),scc[s[tp]]=sc,sz[sc]++,--tp;
	}
}

int a[N],p,in[N];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",str+1);
		for(int j=1;j<=n;j++){
			if(str[j]=='1')
			  add(e,hd1,tot1,i,j);
		}
	}
	for(int i=1;i<=n;i++)
	    if(!dfn[i])
	        tarjan(i);
	        
	for(int u=1;u<=n;u++)
	    for(int i=hd1[u];i;i=e[i].nxt){
	    	int v=e[i].to;
	    	if(scc[u]==scc[v]) continue;
	    	add(E,hd2,tot2,scc[u],scc[v]);
	    	in[scc[v]]++;
	    	
		}
		
	queue<int>que;
	for(int i=1;i<=sc;i++) 
	  if(!in[i])
	    que.push(i);
	    
	while(!que.empty()){
		int u=que.front(); que.pop();
		a[++p]=u;
		for(int i=hd2[u];i;i=E[i].nxt){
			int v=E[i].to;
			if(--in[v]==0) que.push(v);
		}
	}
	for(int t=p;t>=1;t--)
	    for(int i=hd2[a[t]];i;i=E[i].nxt){
	    	int u=a[t],v=E[i].to;
			dp[u]|=dp[v]; 
		} 
		
	int res=0;
	for(int i=1;i<=sc;i++) res+=dp[i].count()*sz[i];
	cout<<res; 
}