在强连通分量的判断中使用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，或许可以在很多类似的题力使用，再修改一下就可以判定动态图的连通性了
点击查看代码[code]#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;        vector  in_index;        vector  out_index;        int x;        int y = 0;        //int b = 1;};void out(int c){        cout  n >> m;        edge edge[1000]; vertex ver[1000];        for (int i = 1; i > edge.v >> edge.x;                ver[edge.v].out_index.push_back(i);                ver[edge.x].in_index.push_back(i);        }                queue  s_y;        ver[1].x = -1; //start from 1 as a root        for (int i = 1; i