【BZOJ 2208】 [Jsoi2010]连通数

浏览数：79 / 时间：2015年06月09日

2208: [Jsoi2010]连通数

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1431 Solved: 585
[Submit][Status][Discuss]

Description

技术分享

Input

输入数据第一行是图顶点的数量，一个正整数N。接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。

Output

输出一行一个整数，表示该图的连通数。

Sample Input

3
010
001
100

Sample Output

HINT

对于100%的数据，N不超过2000。

Source

第一轮

tarjan缩点+拓扑排序+状态压缩

首先缩点，图成为拓扑图。

然后用f[i]表示i与其他点的连通情况（用bitset），f[i][j]=1表示i可以到达j。

按照拓扑序，将i能连到的点j对的f[j]对f[i]整体取或，表示i能到的j也能到。

注意，这样做得到的连通情况是与原图相反的，求出i能到j说明在原图中j能到i。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define M 2000+5
#include <stack>
#include <bitset>
#include <queue>
using namespace std;
queue<int> q;
stack<int> s;
char S[M];
bitset<M> f[M];
int h[M],scc[M],H[M],Tot,tot,du[M],sccno[M],pre[M],lowlink[M];
int n,m,dfs_clock,scc_cnt,v[M][M];
struct edge
{
	int y,ne;
}e[4000005],E[4000005];
void addedge(int x,int y)
{
	e[++tot]=(edge){y,h[x]};
	h[x]=tot;
	du[y]++;
}
void Addedge(int x,int y)
{
	E[++Tot]=(edge){y,H[x]};
	H[x]=Tot;
}
void dfs(int x)
{
	pre[x]=lowlink[x]=++dfs_clock;
	s.push(x);
	for (int i=H[x];i;i=E[i].ne)
	{
		int y=E[i].y;
		if (!pre[y])
		{
			dfs(y);
			lowlink[x]=min(lowlink[x],lowlink[y]);
		}
		else if (!sccno[y])
			    lowlink[x]=min(lowlink[x],pre[y]);
	}
	if (lowlink[x]==pre[x])
	{
		scc_cnt++;
		scc[scc_cnt]=0;
		for (;;)
		{
			int k=s.top();
			s.pop();
			sccno[k]=scc_cnt;
			scc[scc_cnt]++;
			if (k==x) break;
		}
	}
}
void Findscc()
{
	dfs_clock=scc_cnt=0;
	for (int i=1;i<=n;i++)
		if (!pre[i])
			dfs(i);
}
void Rebuild()
{
	for (int x=1;x<=n;x++)
		for (int i=H[x];i;i=E[i].ne)
		{
			int sx=sccno[x],sy=sccno[E[i].y];
			if (sx!=sy&&!v[sx][sy])
				addedge(sx,sy),v[sx][sy]=1;
		}
}
void Topsort()
{
	for (int i=1;i<=scc_cnt;i++)
		f[i][i]=1;
	for (int i=1;i<=scc_cnt;i++)
		if (!du[i]) q.push(i);
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		for (int i=h[x];i;i=e[i].ne)
		{
			int y=e[i].y;
			du[y]--;
			f[y]=f[y]|f[x];
			if (!du[y]) q.push(y);
		}
	}
}
int main()
{
    scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",1+S);
		for (int j=1;j<=n;j++)
			if (i!=j&&S[j]=='1')
				Addedge(i,j);
	}
	Findscc();
	Rebuild();
	Topsort();
	int ans=0;
	for (int i=1;i<=scc_cnt;i++)
		for (int j=1;j<=scc_cnt;j++)
			if (f[i][j])
				ans+=(scc[i]*scc[j]);
	printf("%d\n",ans);
	return 0;
}