Description
Input
输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。
Output
输出一行一个整数，表示该图的连通数。
HINT
对于100%的数据，N不超过2000。
Solution
\(Tarjan\) 缩点 \(+\) 拓扑排序 \(+\) \(bitset\) 优化状压
显然对于每个强联通分量我们都要求出在新图上它能到达哪些点。
如何求呢？
法一： \(dfs\)，对于每个强联通分量找一下它连出去的边能到达哪些联通块，统计答案即可。复杂度 \(O(n^2)\)。(只是口胡一下没有写这种方法如果写不出来别找我)
法二：我们定义数组 \(f[i][j]\) 表示能否从第 \(i\) 个连通分量到达第 \(j\) 个连通分量。因为值只能为 \(0/1\)，我们用 \(bitset\) 来状压第二维。因为 \(f[j]=or(f[i]),j\;can\;go\;to\;i\)，所以我们在新图上建立一张反图，拓扑排序，按照拓扑序即可求出每个点能到达哪些点。 复杂度 \(O(n^2/32)\)。
Code
#include#include #include #include #include #define N 2005#define min(A,B) ((A)<(B)?(A):(B))int ans;char ch[N];bool in[N];int n,cnt,sum,tot;int dfn[N],low[N];std::bitset f[N];std::queue topo;int belong[N],deg[N];int head[N],head2[N];int stk[N],top,sze[N];struct Edge{ int to,nxt;}edge[N*N],edge2[N*N];void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt;}void add2(int x,int y){ edge2[++cnt].to=y; edge2[cnt].nxt=head2[x]; head2[x]=cnt;}int getint(){ int x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x;}void tarjan(int now){ dfn[now]=low[now]=++sum; stk[++top]=now;in[now]=1; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(!dfn[to]){ tarjan(to); low[now]=min(low[now],low[to]); } else if(in[to]) low[now]=min(low[now],dfn[to]); } if(low[now]==dfn[now]){ int y; tot++; do{ y=stk[top--]; belong[y]=tot; sze[tot]++; in[y]=0; }while(y!=now); }}signed main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",ch); for(int j=0;j