Kosaraju Algorithm | pinkyHead's blog

小记

同样作为强连通分量相关的算法，tarjan算法似乎要出名得多，实际上我也是两天前才知道还有个叫Kosaraju的算法。后者与前者的理论复杂度其实是一样的，而且实际情况应用中前者甚至会稍快一些。但是Kosaraju算法有着tarjan所没有的优势——Kosaraju可以与bitset相结合，从而能够在极为优秀的复杂度内解决一些稠密图内的问题。

算法流程

首先对图进行第一遍dfs，并把遍历到的点压入栈中。值得注意的是，这里的压栈要写在dfs函数的最后，即在一个节点及其后继完全访问完毕后再压栈操作。
对这个图求反，即把所有边反向。然后在这个反图上跑dfs。注意这里跑dfs时，选取上一步中栈顶的元素作为起点。一次dfs中遇到的所有点，都属于同一个强连通分量，并且标记他们，注意在dfs过程中，不能访问已经标记过的点。如果dfs结束，那么再次从栈顶取一个未被标记的元素，以它为起点继续在反图上跑dfs，如此往复，直到栈为空。
算法结束，所有的强连通分量已求出。

#include "cstdio"
#include "iostream"
#include "algorithm"

using namespace std ;

const int maxN = 10010 , maxM = 50010;

struct Kosaraju { int to , next ; } ;

Kosaraju E[ 2 ][ maxM ] ;
bool vis[ maxN ];
int head[ 2 ][ maxN ] , cnt[ 2 ] , ord[maxN] , size[maxN] ,color[ maxN ];

int tot , dfs_num  , col_num , N , M  ;

void Add_Edge( int x , int y , int _ ){//建图
         E[ _ ][ ++cnt[ _ ] ].to = y ;
         E[ _ ][ cnt[ _ ] ].next = head[ _ ][ x ] ;
         head[ _ ][ x ] = cnt[ _ ] ;
}

void DFS_1 ( int x , int _ ){
         dfs_num ++ ;//发现时间
         vis[ x ] = true ;
         for ( int i = head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {
                 int temp = E[ _ ][ i ].to;
                 if(vis[ temp ] == false) DFS_1 ( temp , _ ) ;
         }
         ord[(N<<1) + 1 - (++dfs_num) ] = x ;//完成时间加入栈
}

void DFS_2 ( int x , int _ ){
         size[ tot ]++ ;// 强连通分量的大小
         vis[ x ] = false ;
         color[ x ] = col_num ;//染色
         for ( int i=head[ _ ][ x ] ; i ; i = E[ _ ][ i ].next ) {
                 int temp = E[ _ ][ i ].to;
                 if(vis[temp] == true) DFS_2(temp , _);
         }
}

int main ( ){
         scanf("%d %d" , &N , &M );
         for ( int i=1 ; i<=M ; ++i ){
                 int _x , _y ;
                 scanf("%d %d" , &_x , &_y ) ;
                 Add_Edge( _x , _y , 0 ) ;//原图的邻接表
                 Add_Edge( _y , _x , 1 ) ;//逆图的邻接表
         }
         for ( int i=1 ; i<=N ; ++i )
                 if ( vis[ i ]==false )
                          DFS_1 ( i , 0 ) ;//原图的DFS

         for ( int i = 1 ; i<=( N << 1) ; ++i ) {
                 if( ord[ i ]!=0 && vis[ ord[ i ] ] ){
                          tot ++ ; //强连通分量的个数
                          col_num ++ ;//染色的颜色
                          DFS_2 ( ord[ i ] , 1 ) ;
                 }
         }

         for ( int i=1 ; i<=tot ; ++i )
                 printf ("%d ",size[ i ]);
         putchar ('\n');
         for ( int i=1 ; i<=N ; ++i )
                 printf ("%d ",color[ i ]);
         return 0;
}