wordpress 读者墙/百度seo优化软件

割点

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

注意：
1、讨论割点是在无向图中。
2、删除这个点使图的联通分量增多就是割点，所以非连通图也有割点。

割边（桥）

假设有连通图G，e是其中一条边，如果G-e是不连通的，则边e是图G的一条割边。此情形下，G-e必包含两个连通分支。

为什么必包含两个？因为一条边最多连两个点。。。

强推这位大佬的博客，写的非常认真非常详细，非常感谢！

我就不多介绍了，再说就是误导人了

没错我就是来发个模板的，大家可以参考参考，还是满规范的

模板题：P3388 【模板】割点（割顶）

割点割边写起来比缩点还是短不少的。

#include <iostream>
#include <vector>
using namespace std;const int maxn = 10010;
int n, m, id = 0;
int cut[maxn] = {};
vector<int> G[maxn];
int dfn[maxn] = {}, low[maxn];void tarjan(int u, int root)
{int child = 0;dfn[u] = low[u] = ++id;for (size_t i = 0; i < G[u].size(); ++i) {int v = G[u][i];if (dfn[v] == 0) {tarjan(v, root);low[u] = min(low[u], low[v]);if (u != root && low[v] >= dfn[u]) cut[u] = true;if (u == root) child++;}low[u] = min(low[u], dfn[v]);}if (u == root && child >= 2) cut[root] = true;
}int main()
{cin >> n >> m;for (int i = 1; i <= m; ++i) {int x, y;cin >> x >> y;G[x].push_back(y);G[y].push_back(x);}for (int i = 1; i <= n; ++i) {if (dfn[i] == 0) tarjan(i, i);}int ans = 0;for (int i = 1; i <= n; ++i) {if (cut[i]) ans++;}cout << ans << endl;for (int i = 1; i <= n; ++i) {if (cut[i]) cout << i << ' ';}cout << endl;
}

割边（无模板题），换链式前向星来存图。

#include <iostream>
using namespace std;struct Edge {int to, next;
};const int maxn = 10010;
int n, m, id = 0, cnt = 1;
Edge edge[maxn], cut[maxn];
int dfn[maxn] = {}, low[maxn];
int head[maxn] = {}, baba[maxn] = {};
int tou[maxn] = {};void Add(Edge *edge, int u, int v, int *head)
{edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++;
}void tarjan(int u)
{dfn[u] = low[u] = ++id;for (int i = head[u]; i; i = edge[i].next) {int v = edge[i].to;if (baba[u] == v) continue;if (dfn[v] == 0) {baba[v] = u;tarjan(v);low[u] = min(low[u], low[v]);if (low[v] > dfn[u]) Add(cut, u, v, tou);}low[u] = min(low[u], dfn[v]);}
}int main()
{cin >> n >> m;for (int i = 1; i <= m; ++i) {int x, y;cin >> x >> y;Add(edge, x, y, head);Add(edge, y, x, head);}for (int i = 1; i <= n; ++i) {if (dfn[i] == 0) tarjan(i);}for (int u = 1; u <= n; ++u) {for (int i = tou[u]; i; i = cut[i].next) {cout << u << ' ' << cut[i].to << endl;}}
}