专栏文章

scc tarjan + 缩点

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

文章操作

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

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

强连通分量（scc）

定义

强连通：在有向图 GG 中，两个不同的顶点 u,vu,v，即存在 uu 到 vv 的有向路径，也存在 vv 到 uu 的有向路径，则称两个顶点是强连通的。
弱连通：忽略有向图中的方向，如果得到的无向图是连通的，那么原本的图就是弱联通的。
强连通图：在有向图 GG 中，如果每两个节点都相互可达，则称 GG 是一个强连通图。
强连通分量：在有向图中最大的一个强连通子图，子图本身是强连通图，且无法再增加原图中其他任何点。

Tarjan

维护一个栈，以及下列几个变量。
dfnidfn_i 表示点 ii 第一次访问时的时间戳。
lowilow_i 表示点 ii 能回溯到的时间戳最小的节点，且在栈中。
visivis_i 表示点 ii 是否已入栈。

实现步骤

首先，给当前节点的 dfnudfn_u 分配时间戳 timtim，lowulow_u 初始值与 dfnudfn_u 相同。将当前节点入栈，标记 visu=1vis_u = 1。
接下来，枚举当前节点能到达的点 vv。如果 dfnvdfn_v 还没有被分配过时间戳，继续递归到点 vv，因为返回后 vv 的 lowlow 值可能更小，所以更新 lowu=min⁡(lowu,lowv)low_u = \min(low_u, low_v)。否则，判断 vv 是否入栈，即判断 visvvis_v 是否为 11，若是，更新 lowu=min⁡(lowu,dfnv)low_u = \min(low_u, dfn_v)。
最后，判断当前节点是否为强连通分量的入口。当 dfnu=lowudfn_u = low_u 时，证明 uu 是这个强连通分量的入口，弹出栈内所有元素，将栈顶元素的入栈标记清空，这些栈内的元素构成了一个 scc。
C
void tarjan(int u) {
	stk.push(u);
	vis[u] = 1;
	dfn[u] = low[u] = ++tim;
	for (int v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(dfn[v], low[u]);
		}
	}
	if (dfn[u] == low[u]) {
		while (!stk.empty()) {
			vis[stk.top()] = 0;
			if (u == stk.top()) {
				stk.pop();
				break;
			}
			stk.pop();
		}
	}
}

B3609 [图论与代数结构 701] 强连通分量

在原来的基础上，为其每一个 scc 染色，以及存储当前 scc 内的节点，以便后面输出。
C
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int n, m, dfn[N], low[N], col[N], scc, tim;
bool vis[N];
stack<int> stk;
vector<int> nbr[N], v[N];

void tarjan(int u) {
	stk.push(u);
	vis[u] = 1;
	dfn[u] = low[u] = ++tim;
	for (int v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(dfn[v], low[u]);
		}
	}
	if (dfn[u] == low[u]) {
		++scc;
		while (!stk.empty()) {
			col[stk.top()] = scc;
			vis[stk.top()] = 0;
			v[scc].push_back(stk.top());
			if (u == stk.top()) {
				stk.pop();
				break;
			}
			stk.pop();
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		nbr[u].push_back(v); 
	}
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0)
			tarjan(i); 
	}
	cout << scc << '\n';
	for (int i = 1; i <= n; i++) {
		if (dfn[i] == 0)
			continue;
		sort(v[col[i]].begin(), v[col[i]].end());
		for (auto it : v[col[i]]) {
			cout << it << ' ';
			dfn[it] = 0;
		}
		cout << '\n';
	}
	return 0;
}

P2661 [NOIP 2015 提高组] 信息传递

因为每个点只有一条出边，所以最大的强连通分量会是一个环。
所以只需要记录不是一个点的强连通分量个数即可。
C
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m, dfn[N], low[N], col[N], scc, tim, siz[N];
bool vis[N];
stack<int> stk;
vector<int> nbr[N], v[N];

void tarjan(int u) {
	stk.push(u);
	vis[u] = 1;
	dfn[u] = low[u] = ++tim;
	for (int v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(dfn[v], low[u]);
		}
	}
	if (dfn[u] == low[u]) {
		++scc;
		while (!stk.empty()) {
			col[stk.top()] = scc;
			vis[stk.top()] = 0;
			v[scc].push_back(stk.top());
			siz[scc]++;
			if (u == stk.top()) {
				stk.pop();
				break;
			}
			stk.pop();
		}
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		nbr[x].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i);
	}
	int ans = 1e9;
	for (int i = 1; i <= n; i++) {
		if (v[col[i]].size() > 1)
			ans = min(ans, int(v[col[i]].size()));
	}
	cout << ans;
	return 0;
}

P3387 【模板】缩点

缩点其实就是将每一个强连通分量都变成一个点，形成一个 DAG。
定义 sumisum_i 为第 ii 个 scc 里点权的和。
我们只要在弹出栈元素的时候求 sumsum，然后后面进行树形 dp 即可。
C
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 10;

int n, m, dfn[N], low[N], col[N], scc, tim, sum[N], dp[N], a[N], in[N];
bool vis[N];
stack<int> stk;
vector<int> nbr[N], new_nbr[N];
pair<int, int> g[N];

void tarjan(int u) {
	stk.push(u);
	vis[u] = 1;
	dfn[u] = low[u] = ++tim;
	for (int v : nbr[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vis[v]) {
			low[u] = min(dfn[v], low[u]);
		}
	}
	if (dfn[u] == low[u]) {
		++scc;
		while (!stk.empty()) {
			col[stk.top()] = scc;
			vis[stk.top()] = 0;
			sum[scc] += a[stk.top()];
			if (u == stk.top()) {
				stk.pop();
				break;
			}
			stk.pop();
		}
	}
}

void dfs(int u) {
	if (dp[u] != -1)
    return;
	dp[u] = sum[u];
	int maxn = 0;
	for (int v : new_nbr[u]) {
		if (dp[v] == -1){
			dfs(v);
		}
		maxn = max(maxn, dp[v]);
	}
	dp[u] += maxn;
  return;
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		nbr[u].push_back(v);
		g[i] = {u, v};
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i])
			tarjan(i);
	}
  for (int i = 1; i <= m; i++) {
    if (col[g[i].first] != col[g[i].second])
      new_nbr[col[g[i].first]].push_back(col[g[i].second]);
  }
  fill (dp + 1, dp + 1 + n, -1);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (dp[i] == -1) {
      dfs(i);
      ans = max(ans, dp[i]);
    }
  }
  cout << ans;
	return 0;
}
scc缩点并查集缩点edcc（边双缩点）
适用图有向图无向图无向图
缩点之后得到的图的类型DAG无向森林（多棵树）连通图之中直接变成一棵树
一般求解的问题拓扑+dp、2-SAT、环路分析欧拉回路、最小生成树树形 dp

评论

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

正在加载评论...