当前位置: 首页 > news >正文

Kosaraju算法

今天学了Kosaraju算法!曼波

模板:p2863
对于一个图怎么求它有多少个强连通分量呢?!

1,什么是强连通分量?

• 强连通:在一个有向图G中,如果两个顶点u、v间存在
一条u到v的路径且也存在一条v到u的路径,则称这两个
顶点u、v是强连通的
• 强连通图:有向图G的任意两个顶点都强连通,则称G是
一个强连通图
• 极大强连通子图:G是一个极大强连通子图,当且仅当G
是一个强连通子图且不存在另一个强连图子图G’ G
• 强连通分量:有向非强连通图的极大强连通子图,称为
强连通分量;

Kosaraju算法

一种使用两次dfs的求解方法!一次在原图上,一次在反图上;
然后我们在第一次dfs时记录所有结点的退出顺序,并且在第二次在反图上dfs时按照退出顺序的逆序遍历;
这样第二次就是拓扑序从小到大做,每次就能恰好得到一个强连通分量;
代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int t=0,ans=0;
vector<int> g[100005];
vector<int> gp[100005];//存反图
int b[50005],s[50005];
void dfs1(int x){b[x]=1;for(int i=0;i<g[x].size();i++){if(!b[g[x][i]]) dfs1(g[x][i]); }s[++t]=x;//记录退出顺序return;
}
void dfs2(int x){b[x]=1;for(int i=0;i<gp[x].size();i++){if(!b[gp[x][i]]){cnt++;dfs2(gp[x][i]);	}}return;
}
int main(){memset(g,0,sizeof(g));memset(gp,0,sizeof(gp));cin>>n>>m;int x,y;for(int i=1;i<=m;i++){cin>>x>>y;g[x].push_back(y);gp[y].push_back(x);}for(int i=1;i<=n;i++){//第一次dfsif(!b[i]) dfs1(i);}memset(b,0,sizeof(b));for(int i=t;i>=1;i--){//第二次dfscnt=0;if(!b[s[i]]){dfs2(s[i]);if(cnt>0) ans++;//题目要求判断点数大于一} }cout<<ans;return 0;
}

听说tarjan更好呢...题解也全是tarjan
下次再学吧~

http://www.hskmm.com/?act=detail&tid=21690

相关文章:

  • bat批处理设置临时PATH路径不能访问
  • 10. Spring AI + RAG - Rainbow
  • 《AI智能体实战研发教程(从0到企业级项目落地)》全网上线|CSDN B站同步首发
  • 9. Spring AI 当中对应 MCP 的操作 - Rainbow
  • 9/30
  • rhel8无法输入中文问题(红帽8安装中文输入法)
  • 威佐夫博弈(Wythoff‘s Game)
  • C语言⽂件管理讲解(1)
  • 2025年9月30日
  • Min-p采样:通过动态调整截断阈值让大模型文本生成兼顾创造力与逻辑性
  • 2025 年快速卷帘门品牌最新推荐排行榜:聚焦智能定制与高效供货,精选快速卷帘门实力厂家
  • ARL灯塔搭建
  • 记 Charles 抓不到包 - Higurashi
  • STM32H743-ARM例程13-SDIO - 实践
  • 贼猴 0930 模拟赛 T2 | 计数
  • 题解:AT_abc311_h [ABC311Ex] Many Illumination Plans
  • 一个孤单的程序员
  • 根号大杂烩
  • 学习java的第二天
  • 日记.txt
  • Beatty 定理
  • 2025-9-27 提高组模拟赛 div2
  • part2
  • Controversial Rounds
  • 题解:B4410 [GESP202509 一级] 金字塔
  • 9.30总结
  • pytorch基本运算-torch.normal()函数输出多维材料时,如何绘制正态分布函数图
  • AT_agc035_c [AGC035C] Skolem XOR Tree
  • 动手动脑 - A
  • 2025.9.30总结 - A