Kosaraju算法详解

Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单:

(1) 第一次对图G进行DFS遍历,并在遍历过程中,记录每一个点的退出顺序。以下图为例:

    如果以1为起点遍历,访问结点的顺序如下:

结点第二次被访问即为退出之时,那么我们可以得到结点的退出顺序:

(2)倒转每一条边的方向,构造出一个反图G’。然后按照退出顺序的逆序对反图进行第二次DFS遍历。我们按1、4、2、3、5的逆序第二次DFS遍历:

访问过程如下:

每次遍历得到的那些点即属于同一个强连通分量。1、4属于同一个强连通分量,2、3、5属于另一个强连通分量。

 代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int map[101][101];
 6 int nmap[101][101];
 7 int pass[101];
 8 int vis[101];
 9 int now=1;
10 int n,m;
11 int num=0;
12 void dfs(int p)
13 {
14     vis[p]=1;
15     for(int i=1;i<=n;i++)
16     {
17         if(vis[i]==0&&map[p][i]==1)
18         {
19             dfs(i);
20         
21         }
22     }
23     pass[now]=p;
24     now++;
25 }
26 void ndfs(int p)
27 {
28     vis[p]=0;
29     for(int i=1;i<=n;i++)
30     {
31         if(vis[i]==1&&nmap[p][i]==1)
32         ndfs(i);
33     }
34 }
35 int main()
36 {
37     
38     scanf("%d%d",&n,&m);
39     for(int i=1;i<=m;i++)
40     {
41         int x,y;
42         scanf("%d%d",&x,&y);
43         map[x][y]=1;
44         nmap[y][x]=1;
45     }
46     for(int i=1;i<=n;i++)
47     {
48         if(vis[i]==0)
49         dfs(i);
50     }
51     pass[now]=1;
52     for(int i=n;i>=1;i--)
53     {
54         if(vis[pass[i]]==1)
55         {
56             ndfs(pass[i]);
57             num++;
58         }
59     }
60     cout<<num;
61     return 0;
62 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏图形学与OpenGL

WebGL三角形平移变换(矩阵方式)

2601
来自专栏HansBug's Lab

1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

2776
来自专栏小樱的经验随笔

Codeforces Round #301 (Div. 2)(A,【模拟】B,【贪心构造】C,【DFS】)

A. Combination Lock time limit per test:2 seconds memory limit per test:256 mega...

30410
来自专栏chenjx85的技术专栏

leetcode-342-Power of Four

2454
来自专栏编程理解

数据结构(九):广度优先与深度优先

广度优先搜索(breadth-first search)和深度优先搜索(depth-first search)是两种探索图/树中顶点的思路。这两种搜索方式可以用...

1302
来自专栏数据结构与算法

3339: Rmq Problem

Description image.png Input image.png Output image.png Sample Input 7 5 ...

34011
来自专栏xingoo, 一个梦想做发明家的程序员

循环队列

循环队列类似栈,但是有两个口,一个专门用来入队,一个专门用来出队。由于入队出队不在一个端口,因此如果不适用循环队列,随着队列的使用,存储空间马上就被耗光了。在循...

2038
来自专栏小樱的经验随笔

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

4197
来自专栏李家的小酒馆

图的深度优先遍历和广度优先遍历

深度优先遍历 图的深度优先遍历类似于树的先序遍历,首先通过一个指定的节点开始遍历,然后访问第一个邻接点,然后切换到这个节点判断是否是否有邻接点,如果有,判断是否...

2560
来自专栏数据结构与算法

P3385 【模板】负环

题目描述 暴力枚举/SPFA/Bellman-ford/奇怪的贪心/超神搜索 输入输出格式 输入格式: 第一行一个正整数T表示数据组数,对于每组数据: 第一行两...

3145

扫码关注云+社区

领取腾讯云代金券