图的连通性——Tarjan算法&割边&割点
tarjan算法
原理：
我们考虑 DFS 搜索树与强连通分量之间的关系。
如果结点 是某个强连通分量在搜索树中遇到的第⼀个结点，那么这个强连通分量的其余结点肯定 是在搜索树中以 为根的⼦树中。 被称为这个强连通分量的根。
反证法：假设有个结点 在该强连通分量中但是不在以 为根的⼦树中，那么 到 的路径中肯 定有⼀条离开⼦树的边。但是这样的边只可能是横叉边或者反祖边，然⽽这两条边都要求指向的结点已 经被访问过了，这就和 是第⼀个访问的结点⽭盾了。得证。
思路：
在 Tarjan 算法中为每个结点 维护了以下⼏个变量：
1:dfn[u]深度优先搜索遍历时结点 的DFS序。
2:low[u]设以u为根的⼦树为Subtree[u]。low[u]定义为以下结点的dfn的最⼩值：
Subtree(u)中的结点；从 Subtree(u)通过⼀条不在搜索树上的边能到达的结点。
遍历时维护栈，⽤于求解强连通分量。 ⼀个结点的⼦树内结点的 dfn 都⼤于该结点的 dfn。 从根开始的⼀条路径上的 dfn 严格递增，low 严格⾮降。 按照深度优先搜索算法搜索的次序对图中所有的结点进⾏搜索。
在搜索过程中，对于结点u和与其v相邻的结点 考虑 3 种情况：
1. v未被访问：继续对v进⾏深度搜索。在回溯过程中，low[v]⽤low[u]更新 。因为存在从u到v的直接路径，所以v 能够回溯到的已经在栈中的结点,u也⼀定能够回溯到。
2. v被访问过，已经在栈中：即已经被访问过，根据low值的定义（能够回溯到的最早的已经在栈中 的结点），则⽤dfn[u]更新low[v] 。
3. v被访问过，已不在在栈中：说明v已搜索完毕，其所在连通分量已被处理，所以不⽤对其做操作。
代码实现：
void tarjan(int x){ dfn[x]=low[x]= tim;//DFS序的赋值 sta[ top]=x;vis[x]=1;//入栈 sd[x]=x;//如果这个点不是强连通分量，缩点后它还是自己 for(int i=head[x];i;i=eg[i].nex){ int y=eg[i].to; if(!dfn[y]){//v未被访问，继续对v进行深度搜索 tarjan(y); low[x]=min(low[x],low[y]);//回溯，更新low[x]值 } else{ if(vis[y]){//被访问过 low[x]=min(low[x],dfn[y]);//回溯，更新low[x]值 } } if(dfn[x]==low[x]){//找到一个强连通分量 int y; while(y=sta[top--]){//依次出栈 sd[y]=x;//缩点 vis[y]=0;//出栈 if(x==y) break; p[x] =p[y];//点权集中 } } }}
※：缩点后，整张图就变成了一个DAG,所以tarjan常常和拓扑排序一同使用。
例题就不插了，毕竟板子都还没过...
但！
还有一个问题！
目光聚焦到这几行代码：
if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); }///////////////////////////////////////////////////else{ if(vis[y]){ low[x]=min(low[x],dfn[y]); }}
为什么一个括号里是low[y],一个是dfn[y]?
在这里，其实都写low[y]也是正确的，但是在割点割边的时候便是有问题的了。
原因：未出现的邻居，可能会连到之前出现过的点，所以是LOW[]；已经出现的邻居再次出现，就必然是强连通分量图中的一个点，可能是最小时序最小根，取它的DFN，继续计算LOW
割点
定义：
对于⼀个⽆向图，如果把⼀个点删除后这个图的极⼤连通分量数增加了，那么这个点就是这个图 的割点（⼜称割顶）。
通俗理解，如果去掉割点能将这个图割成更多小块，这个点就是割点
原理&实现：
⾸先，我们按照 DFS 序给他打上时间戳（访问的顺序）。
这些信息被我们保存在⼀个叫做 dfn 的数组中。 还需要另外⼀个数组 low ，⽤它来存储不经过其⽗亲能到达的最⼩的时间戳。 例如 low[2] 的话是 1， low[5] 和 low[6] 是 3。 然后我们开始 DFS，我们判断某个点是否是割点的根据是：对于某个顶点 ，如果存在⾄少⼀个顶 点 （ 的⼉⼦），使得low[v]>=dfs[u] ，即不能回到祖先，那么u点为割点。 另外，如果搜到了⾃⼰（在环中），如果他有两个及以上的⼉⼦，那么他⼀定是割点了，如果只有 ⼀个⼉⼦，那么把它删掉，不会有任何的影响。
代码：
#include<bits/stdc .h>using namespace std;const int N=2e5 5;int n,m;int idx=0;int tim;int root;struct node {//邻接表建图 int to; int from; int nex;} eg[N];int head[N];int low[N],dfn[N];int vis[N];int cnt[N];void add(int x,int y) {//建图 eg[ idx].from=x; eg[idx].to=y; eg[idx].nex=head[x]; head[x]=idx;}void tarjan(int x) { low[x]=dfn[x]= tim; vis[x]=1; int flag=0; for(int i=head[x];i;i=eg[i].nex){ int y=eg[i].to; if(!vis[y]) { tarjan(y); low[x]=min(low[y],low[x]); if(low[y]>=dfn[x]) {//回不到更早的祖先节点 flag ;//统计儿子数 if(x!=root||flag>1) {//如果是根节点，要有2个儿子回不到祖先 cnt[x]=1;//标记割点 } } } else low[x]=min(low[x],dfn[y]);//如果y已经被遍历，则low[x]直接更新 }}int main() { cin>>n>>m; for(int i=1; i<=m; i ) { int x,y; cin>>x>>y; add(x,y); add(y,x);//建图 } for(int i=1; i<=n; i ) { if(!vis[i]) { root=i; tarjan(root); } } int ans=0; for(int i=1; i<=n; i ) { ans =cnt[i]; } cout<<ans<<endl; for(int i=1;i<=n;i ) { if(cnt[i]) cout<<i<<" "; } return 0;}
割边
定义：
对于⼀个⽆向图，如果删掉⼀条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨 来说，就是：假设有连通图 G=V,E， 是其中⼀条边（即 e∈E），如果 G-e是不连通 的，则边 e是图 G的⼀条割边（桥）。
通俗来讲，如果去掉边能将这个图割成更多小块，这条边就是割边（桥）
实现：
实现 和割点差不多，只要改⼀处： low[v]>dfn[u]就可以了，⽽且不需要考虑根节点的问题。 原来我们求割点的时候，发现点 v不经过⽗节点 u就⽆法回到祖先节点，所以顶点u 是割点。
对于边来说，如果⼦节点 只能通过当前这条边到达⽗亲节点 ，则说明当前这条边是割边。但是要 注意的是，我们只改上⾯说的那⼀处，会有问题。我们⽤两条边来表示⽆向图的⼀条边，在搜索 的时 候会通过反边往⽗亲 ⾛，如果这个时候更新 的话，将会导致错误。所以需要特判反边（注意，如 果⽤特判⽗亲节点的⽅法规避反边，会在重边图出错）。
代码就懒得打了（其实是不会）