有向图缩点
t a r j a n tarjan tarjan算法求 s c c scc scc缩点
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;
int n, m;
int head[N], edge_end[M], next_edge[M], edge_index;
int dfn[N], low[N], timestamp;
int scc_cnt, id[N], cnt[N];
int stack[N], top;
bool in_stack[N];
int deg[N];
void add(int ver1, int ver2) {
edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], head[ver1] = edge_index++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stack[++top] = u, in_stack[u] = true;
for (int i = head[u]; ~i; i = next_edge[i]) {
int ver = edge_end[i];
if (!dfn[ver]) {
tarjan(ver);
low[u] = min(low[u], low[ver]);
}
else if (in_stack[ver]) low[u] = min(low[u], dfn[ver]);
}
if (dfn[u] == low[u]) {
++scc_cnt;
int ver;
do {
ver = stack[top--];
in_stack[ver] = false;
id[ver] = scc_cnt;
cnt[scc_cnt]++;
}
while (ver != u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
add(u, v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) tarjan(i);
}
for (int u = 1; u <= n; ++u) {
for (int i = head[u]; ~i; i = next_edge[i]) {
int scc1 = id[u];
int scc2 = id[edge_end[i]];
if (scc1 == scc2) continue;
deg[scc1]++;
}
}
int res = 0, tag = 0;
for (int i = 1; i <= scc_cnt; ++i) {
if (!deg[i]) {
if (tag != 0) {
res = 0;
break;
}
res += cnt[i];
tag = 1;
}
}
cout << res << "\n";
return 0;
}
无向图缩点
t a r j a n tarjan tarjan算法求 e − d c c e-dcc e−dcc缩点
任何两点直接至少包含两条互不相交的路径, 等价于是 e − d c c e-dcc e−dcc
- 充分性: 如果不是 e − d c c e-dcc e−dcc, 至少存在一条边是桥, 对于桥两侧的点必须经过桥, 也就不是至少包含两条互不相交的路径, 那么一定是 e − d c c e-dcc e−dcc
- 必要性: 如果图是 e − d c c e-dcc e−dcc, 对于任意两个点 x , y x, y x,y, x , y x, y x,y之间是否至少存在两条互不相交路劲, 因为不包含桥, 因此两点是一定能互相到达的, 也就是至少是三个点的环, 因此必然存在两条互不相交的路径
将原图缩点后, 变为一棵树, 所有度数为 1 1 1 的点都要加边
将所有叶子结点都连接起来, 该图一定是无向连通图, 也就是没有任意一个点是桥
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5010, M = 20010;
int n, m;
int head[N], edge_end[M], next_edge[M], edge_index;
int dfn[N], low[N], timestamp;
int dcc_cnt, id[N];
int stack[N], top;
bool is_bridge[M];
int deg[N];
void add(int ver1, int ver2) {
edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], head[ver1] = edge_index++;
}
void tarjan(int u, int from) {
dfn[u] = low[u] = ++timestamp;
stack[++top] = u;
for (int i = head[u]; ~i; i = next_edge[i]) {
int ver = edge_end[i];
if (!dfn[ver]) {
tarjan(ver, i);
low[u] = min(low[u], low[ver]);
// 如果严格小于, 那么u-v之间的边就是桥
if (dfn[u] < low[ver]) {
is_bridge[i] = is_bridge[i ^ 1] = true;
}
}
else if (i != (from ^ 1)) low[u] = min(low[u], dfn[ver]);
}
if (dfn[u] == low[u]) {
dcc_cnt++;
int ver;
do {
ver = stack[top--];
id[ver] = dcc_cnt;
}
while (ver != u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(head, -1, sizeof head);
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
tarjan(1, -1);
for (int i = 0; i < edge_index; ++i) {
// 如果这条边是桥, 记录度
if (is_bridge[i]) {
int dcc = id[edge_end[i]];
deg[dcc]++;
}
}
int res = 0;
for (int i = 1; i <= dcc_cnt; ++i) {
if (deg[i] == 1) res++;
}
cout << (res + 1) / 2 << "\n";
return 0;
}
t a r j a n tarjan tarjan算法求 v − d c c v-dcc v−dcc缩点
- 统计连通块个数 c n t cnt cnt
- 枚举在哪个连通块中删除
- 枚举删除连通块中的哪个点
假设删除该点后这个连通块会被分割 s s s部分, 那么 a n s = ( s + c n t − 1 ) ans = (s + cnt - 1) ans=(s+cnt−1)
如何计算 s s s, 也就是删除当前点后所在连通分量被分割为的数量?
t a r j a n tarjan tarjan算法求割点, 将当前位置分为是根节点和不是根节点
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010, M = 30010;
int n, m;
int head[N], edge_end[M], next_edge[M], edge_index;
int dfn[N], low[N], timestamp;
int root;
int max_cnt;
void add(int ver1, int ver2) {
edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], head[ver1] = edge_index++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
int cnt = 0;
for (int i = head[u]; ~i; i = next_edge[i]) {
int ver = edge_end[i];
if (!dfn[ver]) {
tarjan(ver);
low[u] = min(low[u], low[ver]);
if (dfn[u] <= low[ver]) cnt++;
}
else low[u] = min(low[u], dfn[ver]);
}
if (u != root) cnt++;
max_cnt = max(max_cnt, cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> n >> m, n || m) {
memset(head, -1, sizeof head);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
edge_index = timestamp = max_cnt = 0;
while (m--) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
int cnt = 0;
for (root = 0; root < n; ++root) {
if (!dfn[root]) {
tarjan(root);
cnt++;
}
}
int res = cnt + max_cnt - 1;
cout << res << "\n";
}
return 0;
}
*点的双连通分量 v − d c c v-dcc v−dcc综合应用
396. 矿场搭建
问题描述: 给定无向连通图, 问至少在几个位置设置出口, 使得无论任意一个点坍塌其余所有点都能走到出口位置
出口数量必须 ≥ 2 \ge 2 ≥2, 如果一个出口坏掉必须还有一个出口
- 因为图可能是不连通的, 因此分别考虑不同连通块, 不同连通块之间是乘法原理
- 如果当前点无割点, 可以任选两个点作为出口, 方案数就是 C c n t 2 C_{cnt} ^ {2} Ccnt2
每个割点至少属于两个双连通分量
考虑上述 v − d c c v-dcc v−dcc情况, 如果当前连通块有割点, 那么需要进行缩点, 然后统计每个 v − d c c v-dcc v−dcc的度数
- 如果某个 v − d c c v-dcc v−dcc的 度数 = 1 度数= 1 度数=1, 必须在 v − d c c v-dcc v−dcc内部(非割点)放一个出口
- 如果 度数 > 1 度数 > 1 度数>1, 无需设置出口, 因为 度数 > 1 度数 > 1 度数>1, 因此在连通分量内部坍塌, 可以走到左右两侧两个割点位置, 如果在割点位置坍塌, 那么可以走到另一个割点位置
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int N = 1010, M = 1010;
int n, m;
int head[N], edge_end[M], next_edge[M], edge_index;
int dfn[N], low[N], timestamp;
int stack[N], top;
int dcc_cnt;
vector<int> dcc[N];
bool is_cut[N];
int root;
void add(int ver1, int ver2) {
edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], head[ver1] = edge_index++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stack[++top] = u;
// 当前点是孤立点
if (u == root && head[u] == -1) {
dcc_cnt++;
dcc[dcc_cnt].push_back(u);
return;
}
// 记录v-dcc数量
int cnt = 0;
for (int i = head[u]; ~i; i = next_edge[i]) {
int ver = edge_end[i];
if (!dfn[ver]) {
tarjan(ver);
low[u] = min(low[u], low[ver]);
// 当前点是割点或者根节点
if (dfn[u] <= low[ver]) {
cnt++;
if (u != root || cnt > 1) is_cut[u] = true;
++dcc_cnt;
int v;
do {
v = stack[top--];
dcc[dcc_cnt].push_back(v);
}
while (v != ver);
// 因为v-dcc包含割点, 因此将当前点u也加入到v-dcc中
dcc[dcc_cnt].push_back(u);
}
}
else low[u] = min(low[u], dfn[ver]);
}
}
int main() {
int T = 1;
while (scanf("%d", &m), m) {
memset(head, -1, sizeof head);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(is_cut, false, sizeof is_cut);
for (int i = 1; i <= dcc_cnt; ++i) dcc[i].clear();
edge_index = timestamp = top = n = dcc_cnt = 0;
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
n = max({
n, u, v});
}
for (root = 1; root <= n; ++root) {
if (!dfn[root]) tarjan(root);
}
// 出口数量和方案数
int res = 0;
ULL ans = 1;
for (int i = 1; i <= dcc_cnt; ++i) {
// 统计连通分量中割点的数量
int cnt = 0;
for (int u : dcc[i]) if (is_cut[u]) cnt++;
if (cnt == 0) {
// 在连通分量内部任选两个点
if (dcc[i].size() > 1) {
res += 2;
int sz = dcc[i].size();
ans *= sz * (sz - 1) / 2;
}
// 孤立点需要单独一个出口
else res++;
}
// 在非割点位置设置一个出口
else if (cnt == 1) {
res++;
ans *= (dcc[i].size() - 1);
}
}
printf("Case %d: %d %llu\n", T++, res, ans);
}
return 0;
}
D S U DSU DSU缩点
用哈希表管理重边的情况, 对边的两个节点做哈希映射, 每个集合由祖宗节点维护全部信息
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <unordered_set>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2e5 + 10, M = N << 1;
int n;
int w[N];
int head1[N], head2[N], edge_end[M], next_edge[M], edge_index;
int fa[N];
bool vis[N];
PII edges[M];
int res;
unordered_set<LL> set;
void add(int head[], int ver1, int ver2) {
edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], head[ver1] = edge_index++;
}
int find(int u) {
if (fa[u] != u) fa[u] = find(fa[u]);
return fa[u];
}
// 合并两个点
void merge(int u, int v) {
int fa1 = find(u);
int fa2 = find(v);
fa[fa2] = fa1;
}
// 求树的直径
int dfs(int u, int fa) {
int d1 = 0, d2 = 0;
for (int i = head2[u]; ~i; i = next_edge[i]) {
int ver = edge_end[i];
if (ver == fa) continue;
int val = dfs(ver, u) + 1;
if (val > d1) d2 = d1, d1 = val;
else if (val > d2) d2 = val;
}
res = max(res, d1 + d2);
return d1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(head1, -1, sizeof head1);
memset(head2, -1, sizeof head2);
cin >> n;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1; i <= n; ++i) cin >> w[i];
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
add(head1, u, v);
add(head1, v, u);
if (w[u] == w[v]) merge(u, v);
edges[i] = {
u, v};
}
for (int i = 0; i < n - 1; ++i) {
int u = find(edges[i].first);
int v = find(edges[i].second);
if (u != v && set.count((LL) u * n + v) == 0 && set.count((LL) v * n + u) == 0) {
add(head2, u, v);
add(head2, v, u);
set.insert((LL) u * n + v);
set.insert((LL) v * n + u);
}
}
dfs(find(n), -1);
cout << res / 2 << "\n";
return 0;
}
京公网安备 11010502036488号