20250819 强连通分量，边双总结
连通性定义
-
连通分量：无向图中所有节点相互连通的子图。
-
弱连通分量：将有向图所有边视为无向边后，所有节点相互连通的子图。
-
强连通分量：有向图中任意两个节点互相连通的子图。
-
点双连通分量：连通子图中删除任一节点后，其余节点仍保持连通。
-
边双连通分量：连通子图中删除任一条边后，其余节点仍保持连通。
强连通分量
一张有向图里，如果一张子图，它包含的节点互相连通并且极大，那么他就是极大强连通子图，也就是强连通分量。
举个栗子(强连通分量)
假设有以下图：
该图有三个强连通分量，分别为{1,2,3}、{4,5,6}、{7}。注意，不能把7归入到第二个强连通分量，因为7和4、5、6并不互相连通。
DFS生成树(搜索树)
在有向图的DFS生成树中存在四种边类型：
- 树边：从父节点指向未被访问的子节点
- 返祖边：指向祖先节点的边
- 前向边：指向子树中的边
- 横叉边：指向已访问过的非祖先非子树节点
需要注意的是，前向边和横叉边仅存在于有向图的DFS树中，无向图中只会有树边和返祖边。
关于DFS生成树与强连通分量的关系：
在一个强连通分量中，若点u是最先被搜索到的节点，则该分量中其余所有节点都必然位于以u为根的子树内。
证明? 反证法
假设强连通分量中存在节点v不在u的子树中。由于u和v互相可达，u到v的路径上必须存在离开子树的边（横叉边或返祖边），这意味着这些边指向的节点已被访问。
但若u和v同属一个强连通分量，这些更早被访问的节点本应能访问到u，这与u是最先被搜索到的假设矛盾，成立。
缩点
找到强连通分量后，可以考虑缩点，也就是把一整个强连通分量压缩成一个点，这样就能使原图变成有向无环图。
可以发现，有向无环图绝不连通，就是不会再有强连通分量。
缩点时要注意原图中的边和新图中的边的对应关系。
举个栗子(缩点)
假设有以下图：
该图有三个强连通分量，分别为{1,2,3}、{4,5,6}、{7}。
缩点之后长这样：
是不是看起来非常的简洁又明了呢？这就是缩点的益处。
实现
void tarjan(int x){//强连通分量dfn[x]=low[x]=++cnt;q.push(x);for(int i=0;i<E[x].size();i++){int v=E[x][i];if(dfn[v]==0){tarjan(v);low[x]=min(low[x],low[v]);}else if(!gp[v]){low[x]=min(low[x],dfn[v]);}}if(low[x]==dfn[x]){gp[x]=++t;ts[t].push_back(x);while(q.top()!=x){gp[q.top()]=t;ts[t].push_back(q.top());q.pop();}q.pop();}
}
void tarjan(int x){//缩点dfn[x]=low[x]=++cnt;s.push(x);for(int i=0;i<E[x].size();i++){int v=E[x][i];if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(!gp[v]){low[x]=min(low[x],dfn[v]);}}if(low[x]==dfn[x]){k++;while(s.top()!=x){gps[k]+=D[s.top()];gp[s.top()]=k;s.pop();}gp[x]=k;dp[k]=gps[k]+=D[x];s.pop(); }
}
int main(){for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);} }for(int i=1;i<=n;i++){for(int j=0;j<E[i].size();j++){int v=E[i][j];if(gp[i]!=gp[v]){e[gp[i]].push_back(gp[v]);rd[gp[v]]++;}}}return 0;
}
边双连通分量
将强连通分量中的有向边改为无向边，即可得到边双连通分量。
这是因为在强连通分量中，任意两点u和v都是相互可达的。当我们将有向边替换为无向边后，任意两点之间必然存在至少两条不同的路径。
需要注意的是，不要将重边合并，否则上述结论将不再成立。
实现
void dfs(int x,int fa){dfn[x]=low[x]=++cnt;s.push(x);for(auto v:E[x]){if(v.second==(fa^1))continue;if(!dfn[v.first]){dfs(v.first,v.second);low[x]=min(low[x],low[v.first]);}else{low[x]=min(low[x],dfn[v.first]);}}if(low[x]==dfn[x]){num++;while(s.top()!=x){ans[num].push_back(s.top());s.pop(); }ans[num].push_back(x);s.pop();}
}
int main(){for(int i=1;i<=n;i++){if(!dfn[i]){dfs(i,0);}}cout<<num<<endl;for(int i=1;i<=num;i++){cout<<ans[i].size();for(int j=0;j<ans[i].size();j++){cout<<" "<<ans[i][j];}cout<<endl;}return 0;
}