题目链接
题目描述
给定一个由 个配送中心和
条单向运输线路组成的物流网络。你需要回答两个问题：
- 在现有网络中，最多能选出多少个配送中心，使得它们之间任意一对都可以互相调度货物（即相互可达）？
- 为了让整个网络成为一个强连通网络（即任意两个配送中心之间都相互可达），最少需要新增多少条运输线路？
解题思路
这是一个典型的图论问题，两个问题都可以通过强连通分量 (Strongly Connected Component, SCC) 来解决。我们可以将物流网络抽象为一个有向图，其中配送中心为顶点，运输线路为有向边。
第一问：最大互通配送中心数量
“任意一对配送中心都可以互相调度货物”的定义，正是图论中强连通分量 (SCC) 的定义。一个 SCC 是有向图中的一个最大的顶点子集，其中任意两个顶点都是相互可达的。
因此，这个问题实际上是在问：图中最大的 SCC 包含多少个顶点？
算法步骤如下：
- 使用 Tarjan 算法 或 Kosaraju 算法 找出图中的所有 SCC。
- 计算每个 SCC 中包含的顶点数量。
- 找出所有 SCC 中顶点数量的最大值，即为第一问的答案。
第二问：最少新增线路
这个问题询问的是，如何用最少的边使一个有向图变得强连通。这同样可以利用 SCC 来解决。
-
缩点：我们将每个 SCC “压缩”成一个单一的超级节点。原图中连接不同 SCC 的边，在缩点后就成为连接这些超级节点的边。这样，原图就被转换成了一个有向无环图 (DAG)，我们称之为缩点图。
-
分析 DAG：现在问题转化为：如何用最少的边使一个 DAG 变成强连通的？
- 一个强连通的 DAG 只能包含一个节点。如果我们的缩点图只有一个节点，说明原图已经强连通，答案为 0。
- 如果 DAG 中有多个节点，我们需要添加边来消除所有的“起点”和“终点”。在 DAG 中，入度为 0 的节点称为源点 (Source)，出度为 0 的节点称为汇点 (Sink)。
- 为了连接整个图，我们需要从汇点连边到源点，将所有分离的路径串成一个大环。
- 设缩点图中有
个源点和
个汇点。要消除所有源点，至少需要
- 我们可以通过连接汇点和源点来同时满足这两个需求。所需的最少边数是
。
算法整体流程
- 构建图：根据输入构建邻接表。
- 求 SCC：运行 Tarjan 算法，得到每个顶点所属的 SCC 编号 (
scc_id) 和 SCC 的总数 (scc_count)。 - 计算第一问：
- 统计每个 SCC 的大小。
- 找出最大的 SCC 大小。
- 计算第二问：
- 如果
scc_count == 1，答案为 0。 - 否则，根据 SCC 建立缩点图，并计算每个 SCC（超级节点）的入度和出度。
- 统计入度为 0 和出度为 0 的 SCC 数量，分别为
- 答案为
- 如果
代码
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<vector<int>> adj;
vector<int> dfn, low, scc_id;
stack<int> st;
vector<bool> on_stack;
int timer, scc_count;
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
on_stack[u] = true;
for (int v : adj[u]) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (on_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++scc_count;
int node;
do {
node = st.top();
st.pop();
on_stack[node] = false;
scc_id[node] = scc_count;
} while (node != u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
adj.resize(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
dfn.assign(n + 1, 0);
low.assign(n + 1, 0);
scc_id.assign(n + 1, 0);
on_stack.assign(n + 1, false);
timer = 0;
scc_count = 0;
for (int i = 1; i <= n; ++i) {
if (dfn[i] == 0) {
tarjan(i);
}
}
// Part 1: Find the size of the largest SCC
vector<int> scc_size(scc_count + 1, 0);
int max_scc_size = 0;
for (int i = 1; i <= n; ++i) {
scc_size[scc_id[i]]++;
}
for (int i = 1; i <= scc_count; ++i) {
max_scc_size = max(max_scc_size, scc_size[i]);
}
cout << max_scc_size << endl;
// Part 2: Find min edges to make the graph strongly connected
if (scc_count == 1) {
cout << 0 << endl;
return 0;
}
vector<int> scc_in_degree(scc_count + 1, 0);
vector<int> scc_out_degree(scc_count + 1, 0);
for (int u = 1; u <= n; ++u) {
for (int v : adj[u]) {
if (scc_id[u] != scc_id[v]) {
scc_out_degree[scc_id[u]]++;
scc_in_degree[scc_id[v]]++;
}
}
}
int sources = 0;
int sinks = 0;
for (int i = 1; i <= scc_count; ++i) {
if (scc_in_degree[i] == 0) {
sources++;
}
if (scc_out_degree[i] == 0) {
sinks++;
}
}
cout << max(sources, sinks) << endl;
return 0;
}
import java.util.*;
class Main {
static List<List<Integer>> adj;
static int[] dfn, low, sccId;
static boolean[] onStack;
static Stack<Integer> stack;
static int timer, sccCount;
static void tarjan(int u) {
dfn[u] = low[u] = ++timer;
stack.push(u);
onStack[u] = true;
for (int v : adj.get(u)) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sccCount++;
int node;
do {
node = stack.pop();
onStack[node] = false;
sccId[node] = sccCount;
} while (node != u);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
adj.get(u).add(v);
}
dfn = new int[n + 1];
low = new int[n + 1];
sccId = new int[n + 1];
onStack = new boolean[n + 1];
stack = new Stack<>();
timer = 0;
sccCount = 0;
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
tarjan(i);
}
}
// Part 1
int[] sccSize = new int[sccCount + 1];
int maxSccSize = 0;
for (int i = 1; i <= n; i++) {
if (sccId[i] > 0) {
sccSize[sccId[i]]++;
}
}
for (int i = 1; i <= sccCount; i++) {
maxSccSize = Math.max(maxSccSize, sccSize[i]);
}
// Handle case where n > 0 but m = 0
if (n > 0 && m == 0) {
maxSccSize = 1;
} else if (n > 0 && maxSccSize == 0) {
maxSccSize = 1;
}
System.out.println(maxSccSize);
// Part 2
if (sccCount <= 1) {
System.out.println(0);
return;
}
int[] sccInDegree = new int[sccCount + 1];
int[] sccOutDegree = new int[sccCount + 1];
for (int u = 1; u <= n; u++) {
for (int v : adj.get(u)) {
if (sccId[u] != sccId[v]) {
sccOutDegree[sccId[u]]++;
sccInDegree[sccId[v]]++;
}
}
}
int sources = 0;
int sinks = 0;
for (int i = 1; i <= sccCount; i++) {
if (sccInDegree[i] == 0) {
sources++;
}
if (sccOutDegree[i] == 0) {
sinks++;
}
}
System.out.println(Math.max(sources, sinks));
}
}
import sys
sys.setrecursionlimit(200005)
adj = {}
dfn, low, scc_id = [], [], []
on_stack = []
stack = []
timer, scc_count = 0, 0
def tarjan(u):
global timer, scc_count
timer += 1
dfn[u] = low[u] = timer
stack.append(u)
on_stack[u] = True
for v in adj.get(u, []):
if dfn[v] == 0:
tarjan(v)
low[u] = min(low[u], low[v])
elif on_stack[v]:
low[u] = min(low[u], dfn[v])
if dfn[u] == low[u]:
scc_count += 1
while True:
node = stack.pop()
on_stack[node] = False
scc_id[node] = scc_count
if node == u:
break
def main():
global adj, dfn, low, scc_id, on_stack, stack, timer, scc_count
try:
n, m = map(int, sys.stdin.readline().split())
except ValueError:
print(0)
print(0)
return
adj = {i: [] for i in range(1, n + 1)}
for _ in range(m):
u, v = map(int, sys.stdin.readline().split())
adj[u].append(v)
dfn = [0] * (n + 1)
low = [0] * (n + 1)
scc_id = [0] * (n + 1)
on_stack = [False] * (n + 1)
stack = []
timer, scc_count = 0, 0
for i in range(1, n + 1):
if dfn[i] == 0:
tarjan(i)
# Part 1
if n == 0:
print(0)
else:
scc_size = [0] * (scc_count + 1)
for i in range(1, n + 1):
if scc_id[i] > 0:
scc_size[scc_id[i]] += 1
max_scc_size = max(scc_size) if scc_size else 1
# if n > 0 and m == 0, every node is an SCC of size 1
if n > 0 and max_scc_size == 0:
max_scc_size = 1
print(max_scc_size)
# Part 2
if scc_count <= 1:
print(0)
return
scc_in_degree = [0] * (scc_count + 1)
scc_out_degree = [0] * (scc_count + 1)
for u in range(1, n + 1):
for v in adj.get(u, []):
if scc_id[u] != scc_id[v]:
scc_out_degree[scc_id[u]] += 1
scc_in_degree[scc_id[v]] += 1
sources = sum(1 for i in range(1, scc_count + 1) if scc_in_degree[i] == 0)
sinks = sum(1 for i in range(1, scc_count + 1) if scc_out_degree[i] == 0)
print(max(sources, sinks))
if __name__ == "__main__":
main()
算法及复杂度
- 算法：强连通分量 (Tarjan 算法) + 缩点
- 时间复杂度：
，其中
是配送中心数量，
是运输线路数量。算法的核心是 Tarjan 算法和对图的遍历，均为线性时间复杂度。
- 空间复杂度：
京公网安备 11010502036488号