BZOJ2208:连通数(强连通 & bitset)
程序员文章站
2024-03-19 12:56:28
...
2208: [Jsoi2010]连通数
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 3376 Solved: 1476
[Submit][Status][Discuss]
Description
Input
输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。
Output
输出一行一个整数,表示该图的连通数。
Sample Input
3
010
001
100
010
001
100
Sample Output
9
HINT
对于100%的数据,N不超过2000。
Source
思路:显然强连通分量里的点可以互达,所以先缩点重建DAG,然后计算DAG里面每个点可以达到的哪些点即可,开始没想到用bitset,因为之前被bitset的效率坑过几次,这里数据量不多就可以用一下。# include <iostream>
# include <cstdio>
# include <vector>
# include <bitset>
using namespace std;
const int maxn = 2e3+30;
vector<int>G[maxn],g[maxn];
bitset<maxn>b[maxn];
char s[maxn][maxn];
int dep[maxn], low[maxn], in[maxn], stk, cnt, tot, ans;
int belong[maxn], num[maxn], st[maxn*2], in_st[maxn], vis[maxn];
void dfs(int u)
{
dep[u] = low[u] = ++cnt;
st[++stk] = u;
in_st[u] = 1;
for(int j=0; j<G[u].size(); ++j)
{
int v = G[u][j];
if(!dep[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(in_st[v] && dep[v] < low[u])
low[u] = dep[v];
}
if(low[u] == dep[u])
{
++tot;
int j;
do
{
j = st[stk--];
belong[j] = tot;
in_st[j] = 0;
++num[tot];
}while(j != u);
}
}
void dfs2(int u)
{
if(vis[u]) return;
vis[u] = 1;
for(int j=0; j<g[u].size(); ++j)
{
int v = g[u][j];
dfs2(v);
b[u] |= b[v];
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; ++i)
{
scanf("%s",s[i]);
for(int j=0; s[i][j]; ++j)
if(s[i][j]-'0')
G[i].push_back(j+1);
}
for(int i=1; i<=n; ++i)
if(!dep[i])
dfs(i);
for(int i=1; i<=n; ++i)
{
for(int k=0; k<G[i].size(); ++k)
{
int j=G[i][k];
if(belong[i] != belong[j])
{
g[belong[i]].push_back(belong[j]);
++in[belong[j]];
}
}
}
for(int i=1; i<=tot; ++i)
b[i][i] = 1;
for(int i=1; i<=tot; ++i)
if(in[i] == 0) dfs2(i);
for(int i=1; i<=tot; ++i)
for(int j=1; j<=tot; ++j)
if(b[i][j]) ans += num[i]*num[j];
printf("%d\n",ans);
return 0;
}