在强连通分量的判断中使用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]