Kosaraju算法(强连通分量)

这个算法我记得好像在好久之前看到过...但是早就忘干净了233

Kosaraju算法是用来求一张有向图的强连通分量的 $O(n+m)$ 的算法。
算法流程:

在原图上跑dfs,记录出栈序。
按照出栈序的倒序在反图上跑dfs,每次dfs出的联通块即为一个强连通分量。

受欢迎的牛代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,m,p[N],cnt,scc,bel[N],d[N],sz[N],ans;bool vis[N];
struct node{
	int ver[N],nxt[N],head[N],tot;
	void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
}F,G;
void dfs1(int x){
	vis[x]=1;
	for(int i=F.head[x],y;i;i=F.nxt[i])
		if(!vis[y=F.ver[i]])dfs1(y);
	p[++cnt]=x;
}
void dfs2(int x){
	vis[x]=1;sz[bel[x]=scc]++;
	for(int i=G.head[x],y;i;i=G.nxt[i])
		if(!vis[y=G.ver[i]])dfs2(y);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		F.add(x,y),G.add(y,x);
	}
	for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);
	memset(vis,0,sizeof(vis));
	for(int i=n;i;i--)if(!vis[p[i]])++scc,dfs2(p[i]);
	for(int i=1,x,y;i<=F.tot;i++)if((x=bel[F.ver[i]])!=(y=bel[G.ver[i]]))d[y]++;
	for(int i=1;i<=scc;i++)if(!d[i])
		if(!ans)ans=sz[i];
		else puts("0"),exit(0);
	printf("%d\n",ans);
	return 0;
}

我对这个算法的理解是感性的2333,因为它这么简洁又清晰,背过也没毛病啊233

在反图上跑dfs时,若 $x$ 可达 $y$ ,首先说明原图中 $y$ 可达 $x$ ,又有 $y$ 在原图中出栈比 $x$ 早,只可能是原图中 $x$ 可达 $y$ 。于是感性理解算法正确233

这个算法复杂度与tarjan一样,又只能解决这一个问题,那么有什么存在的必要呢?我们发现这个算法比tarjan优越的地方在于它的简洁性,不需要维护一堆乱七八糟的东西,只需要dfs就好了。那么我们利用这一点可以做出一些优化。

我们发现这个算法的瓶颈在于寻找与一个点相连的没有访问过的点。那么用bitset优化可以做到 $O(\frac{n^2}{w})$ ,在稠密图(边数为 $n^2$ 级别)上是很大的优化。于是在稠密图求强连通分量的相关问题上可以考虑这个算法。

考试题友好城市

给定一张n个点，m条边的有向图。q次询问，每次给定一个区间[l;r]，问仅保留编号在这个区间内的边时，能互相到达的点对数。
$n\leq150，m\leq300000，q\leq50000$

我们离线莫队维护边集,每次暴力跑一遍,于是可以做到 $O(\frac{n^2q}{32}+q\sqrt m)$ 。注意需要手写bitset。

关于快速取出一个1的操作我们其实有a._Find_first这个函数,但是它貌似是开头下划线。。。而且我们手写就变快,又不难,何不手写?

这里快速取出一个1的骚操作要讲一下。对于一个unsigned int类型的数要求出它二进制下最低位的1,怎么做呢?我们发现 $2^0,2^1,...2^{31}\%37$ 不同余,于是就可以求出 $lowbit$ 之后再哈希啦!

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+50,M=160;
struct Bitset{
    unsigned v[5];
    void reset(){v[0]=v[1]=v[2]=v[3]=v[4]=0;}
    void flip(int x){v[x>>5]^=1u<<(x&31);}
    int test(int x){return v[x>>5]>>(x&31)&1;}
}e[M],ie[M],vis;
int n,m,q,x[N],y[N],bel[N],sq,l,r,ans[N],num[M][M],b[40],p[N],cnt,sz;
struct node{int l,r,id;bool friend operator <(node a,node b){return bel[a.l]!=bel[b.l]?a.l<b.l:bel[a.l]&1?a.r<b.r:a.r>b.r;}}Q[N];
void insert(int id){if(!num[x[id]][y[id]]++)e[x[id]].flip(y[id]),ie[y[id]].flip(x[id]);}
void erase(int id){if(!--num[x[id]][y[id]])e[x[id]].flip(y[id]),ie[y[id]].flip(x[id]);}
void dfs1(int x){
    vis.flip(x);
    for(int i=0;i<5;i++)
        while(1){
            unsigned p=~vis.v[i]&e[x].v[i];
            if(!p)break;dfs1(i<<5^b[(p&-p)%37]);
        }
    p[++cnt]=x;
}
void dfs2(int x){
    vis.flip(x);sz++;
    for(int i=0;i<5;i++)
        while(1){
            unsigned p=~vis.v[i]&ie[x].v[i];
            if(!p)break;dfs2(i<<5^b[(p&-p)%37]);
        }
}
int solve(){
    int ret=0;vis.reset();cnt=0;
    for(int i=1;i<=n;i++)if(!vis.test(i))dfs1(i);
    vis.reset();
    for(int i=n;i;i--)if(!vis.test(p[i]))
        sz=0,dfs2(p[i]),ret+=sz*(sz-1)/2;
    return ret;
}
int main(){
    for(int i=0;i<32;i++)b[(1u<<i)%37]=i;
    scanf("%d%d%d",&n,&m,&q);sq=sqrt(m);
    for(int i=1;i<=m;i++)bel[i]=(i-1)/sq+1;
    for(int i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=q;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
    sort(Q+1,Q+q+1);insert(l=r=1);
    for(int i=1;i<=q;i++){
        int L=Q[i].l,R=Q[i].r;
        while(l>L)insert(--l);
        while(r<R)insert(++r);
        while(l<L)erase(l++);
        while(r>R)erase(r--);
        ans[Q[i].id]=solve();
    }
    for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
    return 0;
}

Prutekoi's blog

Kosaraju算法(强连通分量)

强竞有哈回