【割点】【割边】tarjan

洛谷割点模板题——传送门

割边：在连通图中，删除了连通图的某条边后，图不再连通。这样的边被称为割边，也叫做桥。
割点：在连通图中，删除了连通图的某个点以及与这个点相连的边后，图不再连通。这样的点被称为割点。
DFS搜索树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树。

树边：在搜索树中的蓝色线所示，可理解为在DFS过程中访问未访问节点时所经过的边，也称为父子边
回边：在搜索树中的橙色线所示，可理解为在DFS过程中遇到已访问节点时所经过的边，也称为返祖边、后向边
观察DFS搜索树，我们可以发现有两类节点可以成为割点。对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；对非叶子节点u(非根节点)，若其中的某棵子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与该棵子树的节点不再连通；则节点u为割点。对于根结点，显然很好处理；但是对于非叶子节点，怎么去判断有没有回边是一个值得深思的问题。我们用dfn[u]记录节点u在DFS过程中被遍历到的次序号，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点(即DFS次序号最小)，那么low[u]的计算过程如下。

对于给的例子，其求出的dfn和low数组如下。
id 1 2 3 4 5 6
dfn 1 2 3 4 5 6
low 1 1 1 4 4 4
可以发现，对于情况2，当(u,v)为树边且low[v]≥dfn[u]时，节点u才为割点。而当(u,v)为树边且low[v]>dfn[u]时，表示v节点只能通过该边(u,v)与u连通，那么(u,v)即为割边。tarjan算法的时间复杂度是O(n+m)的，非常快。

——附带码

#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 100001; int n, m, cnt, rp; int next[2 * maxn], to[2 * maxn], head[maxn], low[maxn], dfn[maxn], father[maxn];//father为父节点 vector <int> cut_point; vector < pair <int, int> > cut_edge; void add(int x, int y) void tarjan(int u) else if(v != father[u]) low[u] = min(low[u], dfn[v]); } //根节点若有两棵或两棵以上的子树则该为割点 //非根节点若所有子树节点均没有指向u的祖先节点的回边则为割点 if((father[u] == 0 && child > 1) || (father[u] && flag)) cut_point.push_back(u); } int main() for(i = 1; i <= n; i++)//图可能不联通（mdzz的洛谷模板题） if(!dfn[i]) tarjan(i); sort(cut_point.begin(), cut_point.end()); s = cut_point.size(); printf("%d\n", s); for(i = 0; i < s; i++) printf("%d ", cut_point[i]);//输出割点 s = cut_edge.size(); printf("\n%d\n", s); for(i = 0; i < s; i++) printf("%d %d\n", cut_edge[i].first, cut_edge[i].second);//输出割边 return 0; }
View Code

经过培训，发现上面的代码如果有重边就会拉闸。

下面是可以应对重边的代码

1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <cmath> 6 # include <vector> 7 # include <map> 8 # include <queue> 9 # include <cstdlib> 10 # define MAXN 2333 11 using namespace std; 12 13 inline void File() 21 22 inline int get_num() 29 30 int n, m, tim, cnt; 31 int dfn[MAXN], low[MAXN], f[MAXN], to[MAXN], next[MAXN], head[MAXN]; 32 vector <int> cut_point; 33 vector < pair <int, int> > cut_edge; 34 35 inline void add(int x, int y) 36 41 42 inline void dfs(int u, int fa) 43 60 else low[u] = min(low[u], dfn[v]); 61 } 62 if((!f[u] && child > 1) || (f[u] && flag)) cut_point.push_back(u); } 64 65 int main() 66 78 for(i = 1; i <= n; i++) 79 if(!dfn[i]) 80 dfs(i, 1); 81 for(i = 0; i < cut_point.size(); i++) printf("%d\n", cut_point[i]); 82 puts(""); 83 for(i = 0; i < cut_edge.size(); i++) printf("%d %d\n", cut_edge[i].first, cut_edge[i].second); 84 puts(""); 85 return 0; 86 }
View Code

上一篇：[USACO11NOV]牛的障碍Cow Steeplechase（匈牙利算法）

下一篇：字典树 Trie树

---

模板 tarjan 割边 割点