题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2208
题意：定义一种连通数，一个点能通过边到达另一个点就是一个连通个数，规定点自己能到达自己，问每个点连通数之和是多少？
思路：首先避免有环，要先用tarjan缩点，并记录每个连通分量的点数。再反向建边，最后拓扑排序求连通分量之间是否可以达到。可以到达，答案加上两连通分量之积即可。
为什么是反向建边呢？
因为正向建边不能保证记录前面的连通分量通过 之后的连通分量 到达其他连通分量， 而反向是可以的。
例如：（正向建图，这里一个点代表一个连通分量）
可以通过拓扑排序，首先进入 1，可以知道 1连接 2 和3，但是马上1就出队列了，无法判定1连接4和5
反向建图：
反向后，可以通过，4,5连向3 记录，3连向4,5 在继续传递，3连向1时，就记录了4,5也连向1，就解决了 1 无法记录的问题。
这里用bitset容器 记录 连通分量之间是否连接。
代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #include<bitset> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=2100; struct node{ int u,v,nxt; }e[maxn*maxn],e1[maxn*maxn]; int h[maxn],h1[maxn],dfn[maxn],low[maxn]; int st[maxn],belong[maxn],val[maxn],vis[maxn],in[maxn]; int cnt,cnt1,tot,top,num,scc,n,m; bitset<maxn> lin[maxn]; void add(int u,int v) { e[cnt].u=u;e[cnt].v=v; e[cnt].nxt=h[u];h[u]=cnt++; } void add1(int u,int v) { e1[cnt1].u=u;e1[cnt1].v=v; e1[cnt1].nxt=h1[u];h1[u]=cnt1++; } void init() { memset(h,-1,sizeof(h)); memset(h1,-1,sizeof(h1)); memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong)); memset(val,0,sizeof(val)); memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); for(int i=1;i<=n;i++) lin[i][i]=1;//初始化，连通分量自己可以连接自己 cnt=cnt1=num=top=tot=scc=0; } void tarjan(int u)//缩点 { low[u]=dfn[u]=++tot; st[++top]=u; vis[u]=1; for(int i=h[u];i!=-1;i=e[i].nxt) { int v=e[i].v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { int t; num++; scc=0; do{ t=st[top--]; vis[t]=0; belong[t]=num; scc++; }while(t!=u); val[num]=scc;//记录每个连通分量点的个数 } } void topsort()//拓扑排序 { int ans=0; queue<int> q; for(int i=1;i<=num;i++) if(in[i]==0) q.push(i); while(!q.empty()) { int u=q.front();q.pop(); for(int i=h1[u];i!=-1;i=e1[i].nxt) { int v=e1[i].v; in[v]--; lin[v]|=lin[u];//或运算，记录连通分量连接情况。 //可以保证之前与u连接的连通分量，v也连接 if(in[v]==0) q.push(v); } } for(int i=1;i<=num;i++) for(int j=1;j<=num;j++) if(lin[i][j])//两个连通分量相连 ans+=val[i]*val[j]; printf("%d ",ans); } char s[maxn]; int main() { scanf("%d",&n); init(); for(int i=1;i<=n;i++) { scanf("%s",s); for(int j=0;j<n;j++) { if(s[j]=='1') add(i,j+1); } } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=0;i<cnt;i++) { if(belong[e[i].u]!=belong[e[i].v]) { add1(belong[e[i].v],belong[e[i].u]);//反向建边 in[belong[e[i].u]]++; } } topsort(); return 0; }