在强连通分量的判断中使用BFS
先理清楚概念：与无向图有关的是块，与有向图有关的是强连通分量强连通分量：分量中任意两点都能相互可达
问题：在有向图中寻找某个顶点所在的的强连通分量，洛谷模板题
输入：n个点，m条边，m行输入 v x
想法：假设要找0所在的强连通分量，可能存在两种性质的点 X：由0点可达的点 Y：能到达0点的点
情形1：若存在可到达0的点，那么从该点开始在反图中进行BFS，遍历到的点都打上Y标记，结束后再从0开始BFS（原图），遍历到的点打上X标记，X和Y重合的点就是与0点在同一强连通分量内的点
情形2：不存在可到达0的点，也就是没有入度，那0点本身就是一个强连通分量
情形3：不存在可从0点出法能到达的点，也就是没有出度，那0点本身就是一个强连通分量
证明：由于强连通分量内的点两两相互可达，存在v和x，若它们相对于0点都具有重合的xy性质，那么存在路径（v, 0）(0, v), (x, 0), (0, x)，也就存在（v，0，x）与（x，0，v）两条路径致使x与v相互可达
若将0点换为任意顶点，则可以查找所有的强连通分量
此方法部分受 Kosaraju 算法的启发，算是我想了小半个月的结果，但是测试下来
洛谷强连通分量链接：https://www.luogu.com.cn/problem/B3609
这是ACcode，或许可以在很多类似的题力使用，再修改一下就可以判定动态图的连通性了
点击查看代码#include #include #include #include#include #include #define typedef#define max 100001using namespace std;typedef struct edge{ int v; int x;};typedef struct vertex{ int v = 1; vectorin_index; vectorout_index; int x; int y = 0; //int b = 1;};void out(int c){ coutn >> m; edge edge; vertex ver; for (int i = 1; i > edge.v >> edge.x; ver.v].out_index.push_back(i); ver.x].in_index.push_back(i); } queues_y; ver.x = -1; //start from 1 as a root for (int i = 1; i 谢谢分享，试用一下 感谢发布原创作品，程序园因你更精彩 谢谢分享，辛苦了 感谢，下载保存了 感谢分享，下载保存了，貌似很强大 用心讨论，共获提升！ 分享、互助 让互联网精神温暖你我 感谢，下载保存了 谢谢楼主提供！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 谢谢楼主提供！ 前排留名，哈哈哈 这个有用。 感谢发布原创作品，程序园因你更精彩 谢谢分享，试用一下 热心回复！ 不错，里面软件多更新就更好了 谢谢分享，辛苦了 东西不错很实用谢谢分享
页:
[1]
2