专栏文章

tarjan 割点 割边

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miooisqj
此快照首次捕获于
2025/12/02 22:34
3 个月前
此快照最后确认于
2025/12/02 22:34
3 个月前
查看原文

割点的定义

对于一个无向图，删除一个点，图的极大联通分量增加，这个点就是一个割点。

实现步骤

很容易想到的是，暴力枚举每一条边和点，但时间复杂度太高，考虑优化。
我们可以使用 Tarjan，记录 dfnidfn_i 为第 ii 个点的时间戳，lowilow_i 表示通过回边（非父子边）能回到的最小时间戳的节点。
对于根节点，若其有两棵及以上的子树，则根节点为割点。
因为如果去掉根节点，两棵子树将无法互相连通。
对于不是根节点的 uu，若有一儿子节点 vv，无法通过回边回到除 uu 外的其他父亲节点，则 uu 为割点，即 lowv≥dfnulow_v \geq dfn_u。

P3388 【模板】割点（割顶）

CPP
#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 10;

int n, m, dfn[N], low[N], tim, root, cnt;
bool vis[N];
vector<int> nbr[N];

void tarjan(int u) {
	int sum = 0;
	dfn[u] = low[u] = ++tim;
	for (int v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				sum++;
				if (u != root || sum >= 2)
					(vis[u] == 0) && (cnt++, vis[u] = 1);
			}
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		nbr[u].push_back(v);
		nbr[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			root = i, tarjan(i);
	}
	cout << cnt << '\n';
	for (int i = 1; i <= n; i++) {
		if (vis[i])
			cout << i << ' ';
	}
	return 0;
}

HDU-4738 Caocao's Bridges

问题转化后即求边权最小值。
注意数组范围，本题很迷。
C
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e3 + 10;

int n, m, head[N], dfn[N], low[N], tim, tot, ans;
bool bridge[2 * N * N];

struct Edge {
	int v, nxt, w;
} edges[N * N * 2];

void add_edge(int u, int v, int w) {
	edges[++tot].v = v;
	edges[tot].nxt = head[u];
	edges[tot].w = w;
	head[u] = tot;
}

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tim;
	for (int i = head[u]; i; i = edges[i].nxt) {
		int v = edges[i].v;
		if (!dfn[v]) {
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) {
				bridge[i] = bridge[i ^ 1] = 1;
			}
		} else if (i != (fa ^ 1)) {
			low[u] = min(low[u], dfn[v]);
		}	
	}
}

signed main() {
	while (cin >> n >> m && n) {
		memset (dfn, 0, sizeof dfn);
		memset (head, 0, sizeof head);
		memset (bridge, 0, sizeof bridge);
		tot = 1, tim = 0;
		int pre = 1e9;
		for (int i = 1; i <= m; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			add_edge(u, v, w), add_edge(v, u, w);
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!dfn[i])
				cnt++, tarjan(i, 0);
		}
		if (cnt >= 2) {
			cout << "0\n";
		} else {
			for (int j = 2; j <= tot; j += 2) {
				if (bridge[j])
					pre = min(pre, edges[j].w);
			}
			if (pre == 1e9)
				cout << "-1\n";
			else if (pre == 0)
				cout << 1 << '\n';
			else
				cout << pre << '\n';
		}
	}
	return 0;
}

割边（桥）定义

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

实现步骤

跟割点没差什么，不用考虑根节点问题，只要改成 lowv>dfnulow_v > dfn_u 即可。

U132350 【模板】割边（桥）

C
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, dfn[N], low[N], tim, root, cnt;
bool vis[N];
vector<int> nbr[N];

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tim;
	for (int v : nbr[u]) {
		if (v == fa)
			continue;
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) {
				cnt++;
			}
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		nbr[u].push_back(v);
		nbr[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i, 0);
	}
	cout << cnt;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...