Kosaraju算法求强联通分量-学习笔记

# bitset._Find_first 函数可以返回bitset的lowbit！！！不用手写啦！！！ Kosaraju算法：$O(n^2/w)$ Tarjan算法：$O(n+m)$ 故Tarjan算法适合稀疏图，Kos（以下简称）适合稠密图 算法流程： [Blog1](https://www.cnblogs.com/nullzx/p/6437926.html) [Blog2](http://wuvin.lofter.com/post/1dcf22f2_9dca761) ------------- ## 算法  考虑求这张图的强联通分量。如果我们把SCC缩点，那么就形成了DAG。如果我们按照DAG的逆拓扑序dfs，每次只走没遍历过的点，每次走出的就是一个SCC！以上图为例，我们先访问B，再访问A，就得到了两个SCC。 那么我们怎么求出这个访问的顺序呢？我们只需要保证被指向的强连通分量的至少一个顶点排在指向这个连通分量的所有顶点前面即可。 我们建出反向边的图，然后以任意顺序dfs，求出后序遍历，逆序后就是合法的顺序。 然后dfs一边就可以得到SCC了。 ```cpp int st[N],tp; void dfs(int x) { B t; abl[x]=0; while((t=re[x]&abl).any()) { int v=t._Find_first(); dfs(v); } st[tp++]=x; } int efs(int x) { int sz=1; B t; abl[x]=0; while((t=e[x]&abl).any()) { int v=t._Find_first(); sz+=efs(v); } return sz; } void Kos(int &res) { abl.set(); tp=0; for(ri i=0; i<n; ++i) if(abl[i]) dfs(i); abl.set(); for(ri i=n-1; i>=0; --i) if(abl[st[i]]) { int t=efs(st[i]); res+=t*(t-1)/2; } } ``` 例题：BZOJ5218 友好城市。莫队+Kos