题目链接
题目描述
在一个员工网络中，一些员工愿意将激活码分享给另一些员工。这种分享关系是具有传递性的。求最少需要购买多少个激活码，才能保证每位员工都拥有激活码。
解题思路
这是一个经典的图论问题，可以通过寻找图中的强连通分量 (Strongly Connected Components, SCC) 来解决。
图论建模
- 节点：将每位员工看作图中的一个节点。
- 有向边：如果员工
u愿意将激活码分享给员工v，我们就建立一条从u到v的有向边u -> v。
强连通分量 (SCC)
- 定义：在有向图中，如果一个顶点子集中，任意两个顶点都互相可达，则这个子集被称为一个强连通分量。
- 关键性质：在一个 SCC 内部，只要有一个员工获得了激活码，这个激活码就可以通过分享传递给该 SCC 内的所有其他员工。因此，一个 SCC 只需要一个激活码。
缩点与求解
- 缩点：我们可以将每个 SCC “压缩”成一个单一的“超级节点”。这样，原来的有向图就变成了一个由这些超级节点组成的有向无环图 (DAG)。
- 寻找源头：在这个缩点后的 DAG 中，我们需要找到那些没有入边的超级节点。一个超级节点（即一个 SCC）如果没有入边，意味着没有任何其他员工群体可以将激活码分享给他们。因此，这个群体必须自己获得一个初始的激活码。这些入度为0的超级节点就是激活码的“源头”。
- 答案：最少需要购买的激活码数量，就等于缩点后 DAG 中入度为0的节点的数量。
算法实现
- 找出 SCC：使用 Tarjan 算法或 Kosaraju 算法可以高效地找出图中所有的 SCC。这两个算法的时间复杂度都是线性的
。
- 计算入度：在找到所有 SCC 后，我们遍历原图的每一条边
(u, v)。如果u和v不属于同一个 SCC，那么这条边就在缩点后的 DAG 中构成了一条从SCC(u)到SCC(v)的边。我们据此统计每个 SCC 的入度。 - 统计结果：最后，统计入度为0的 SCC 数量即为答案。
代码
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], scc_id[MAXN];
bool in_stack[MAXN];
stack<int> st;
int n, m, timer, scc_count;
void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
in_stack[u] = true;
for (int v : adj[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
scc_count++;
int node;
do {
node = st.top();
st.pop();
in_stack[node] = false;
scc_id[node] = scc_count;
} while (node != u);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tarjan(i);
}
}
vector<int> in_degree(scc_count + 1, 0);
for (int u = 1; u <= n; ++u) {
for (int v : adj[u]) {
if (scc_id[u] != scc_id[v]) {
in_degree[scc_id[v]]++;
}
}
}
int zero_in_degree_count = 0;
for (int i = 1; i <= scc_count; ++i) {
if (in_degree[i] == 0) {
zero_in_degree_count++;
}
}
cout << zero_in_degree_count << endl;
return 0;
}
import java.util.*;
import java.io.*;
public class Main {
static List<List<Integer>> adj;
static int[] dfn, low, sccId;
static boolean[] inStack;
static Stack<Integer> st;
static int n, m, timer, sccCount;
static void tarjan(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
inStack[u] = true;
for (int v : adj.get(u)) {
if (dfn[v] == 0) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
sccCount++;
int node;
do {
node = st.pop();
inStack[node] = false;
sccId[node] = sccCount;
} while (node != u);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st_in = new StringTokenizer(br.readLine());
n = Integer.parseInt(st_in.nextToken());
m = Integer.parseInt(st_in.nextToken());
adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
st_in = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st_in.nextToken());
int v = Integer.parseInt(st_in.nextToken());
adj.get(u).add(v);
}
dfn = new int[n + 1];
low = new int[n + 1];
sccId = new int[n + 1];
inStack = new boolean[n + 1];
st = new Stack<>();
timer = 0;
sccCount = 0;
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) {
tarjan(i);
}
}
int[] inDegree = new int[sccCount + 1];
for (int u = 1; u <= n; u++) {
for (int v : adj.get(u)) {
if (sccId[u] != sccId[v]) {
inDegree[sccId[v]]++;
}
}
}
int zeroInDegreeCount = 0;
for (int i = 1; i <= sccCount; i++) {
if (inDegree[i] == 0) {
zeroInDegreeCount++;
}
}
System.out.println(zeroInDegreeCount);
}
}
import sys
# It's necessary to increase recursion limit for deep graphs
sys.setrecursionlimit(200005)
def solve():
try:
n, m = map(int, sys.stdin.readline().split())
except ValueError:
return
adj = [[] for _ in range(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)
in_stack = [False] * (n + 1)
stack = []
timer = 0
scc_count = 0
def tarjan(u):
nonlocal timer, scc_count
timer += 1
dfn[u] = low[u] = timer
stack.append(u)
in_stack[u] = True
for v in adj[u]:
if dfn[v] == 0:
tarjan(v)
low[u] = min(low[u], low[v])
elif in_stack[v]:
low[u] = min(low[u], dfn[v])
if dfn[u] == low[u]:
scc_count += 1
while True:
node = stack.pop()
in_stack[node] = False
scc_id[node] = scc_count
if node == u:
break
for i in range(1, n + 1):
if dfn[i] == 0:
tarjan(i)
if scc_count == 0:
print(n) # Handles case n > 0, m = 0
return
in_degree = [0] * (scc_count + 1)
for u in range(1, n + 1):
for v in adj[u]:
if scc_id[u] != scc_id[v]:
in_degree[scc_id[v]] += 1
zero_in_degree_count = 0
for i in range(1, scc_count + 1):
if in_degree[i] == 0:
zero_in_degree_count += 1
print(zero_in_degree_count)
solve()
算法及复杂度
- 算法：Tarjan 算法求强连通分量 + 缩点 + 入度统计
- 时间复杂度：
是员工数，
是分享关系数。Tarjan 算法、建图、统计入度都可以在线性时间内完成。
- 空间复杂度：
京公网安备 11010502036488号