题目链接
题目描述
在一家有 名员工的公司里，存在
条单向的直接信任关系
u -> v (u 信任 v)。这种信任关系具有传递性，即如果 A 信任 B 且 B 信任 C，则 A 也信任 C。
如果一名员工被所有（包括他自己）员工信任，那么他被称为“核心信任者”。你需要计算公司里核心信任者的数量。
解题思路
这是一个典型的图论问题。我们可以将员工和信任关系抽象为一个有向图，然后通过分析图的结构来找出核心信任者。
1. 图的建模
- 节点 (Nodes)：每位员工是一个节点。
- 边 (Edges)：每条信任关系
u -> v是一条从u指向v的有向边。 - 传递性：
A信任C的条件，在图论中等价于存在一条从A到C的路径。 - 核心信任者：一个员工
X是核心信任者，当且仅当对于图中所有的员工i，都存在一条从i到X的路径。
2. 利用强连通分量 (SCC)
“所有节点都能到达 X” 这个条件，让我们联想到图的连通性。我们可以通过强连通分量 (Strongly Connected Component, SCC) 来简化问题。
- SCC：在有向图中，一个 SCC 是一个最大的节点子集，其中任意两个节点都可以相互到达。
- 缩点：我们可以将每个 SCC “压缩”成一个单一的超级节点。所有这些超级节点和它们之间的连接关系构成了一个新的、更简单的图——缩点图。这个缩点图一定是一个有向无环图 (DAG)。
3. 在缩点图上分析
- 如果员工
X是核心信任者，那么他所在的 SCC（记为S_X）必须能被所有其他 SCC 到达。 - 在一个 DAG 中，如果一个节点能被所有其他节点到达，那么这个节点必须是唯一的汇点（Sink），即它的出度必须为 0。
- 为什么？如果
S_X有一条出边指向另一个 SCC（记为S_Y），那么S_Y中的节点就无法回到S_X（因为缩点图是无环的），这与“所有员工都信任X”的条件相悖。 - 为什么必须是唯一的汇点？如果存在另一个出度为 0 的 SCC（记为
S_Z），那么S_Z中的节点也无法到达S_X，同样不满足条件。
- 为什么？如果
4. 算法流程
- 构建图：根据输入的信任关系，构建一个有向图。
- 求 SCC：使用 Tarjan 算法 将图分解为若干个 SCC。
- 计算缩点图的出度：
- 遍历原图中的每一条边
(u, v)。 - 如果
u和v属于不同的 SCC（即scc_id[u] != scc_id[v]），那么这条边就在缩点图上构成了一条从SCC_u到SCC_v的边。此时，我们将SCC_u的出度加 1。
- 遍历原图中的每一条边
- 寻找唯一的汇点：
- 统计缩点图中出度为 0 的 SCC 的数量。
- 如果数量恰好为 1，那么这个唯一的汇点 SCC 中的所有员工都是核心信任者。答案就是这个 SCC 的大小。
- 如果数量不为 1（0 个或多个），则说明不存在任何核心信任者，答案为 0。
代码
#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);
}
}
vector<int> scc_out_degree(scc_count + 1, 0);
vector<int> scc_size(scc_count + 1, 0);
for (int u = 1; u <= n; ++u) {
scc_size[scc_id[u]]++;
for (int v : adj[u]) {
if (scc_id[u] != scc_id[v]) {
scc_out_degree[scc_id[u]]++;
}
}
}
int sink_count = 0;
int sink_scc_id = -1;
for (int i = 1; i <= scc_count; ++i) {
if (scc_out_degree[i] == 0) {
sink_count++;
sink_scc_id = i;
}
}
if (sink_count == 1) {
cout << scc_size[sink_scc_id] << endl;
} else {
cout << 0 << 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);
}
}
// Handle case with no edges and n > 0
if (sccCount == 0 && n > 0) {
System.out.println(0);
return;
}
int[] sccOutDegree = new int[sccCount + 1];
int[] sccSize = new int[sccCount + 1];
for (int u = 1; u <= n; u++) {
sccSize[sccId[u]]++;
for (int v : adj.get(u)) {
if (sccId[u] != sccId[v]) {
sccOutDegree[sccId[u]]++;
}
}
}
int sinkCount = 0;
int sinkSccId = -1;
for (int i = 1; i <= sccCount; i++) {
if (sccOutDegree[i] == 0) {
sinkCount++;
sinkSccId = i;
}
}
if (sinkCount == 1) {
System.out.println(sccSize[sinkSccId]);
} else {
System.out.println(0);
}
}
}
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: # Handles empty input
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)
if scc_count == 0 and n > 0:
print(0)
return
scc_out_degree = [0] * (scc_count + 1)
scc_size = [0] * (scc_count + 1)
for u in range(1, n + 1):
scc_size[scc_id[u]] += 1
for v in adj.get(u, []):
if scc_id[u] != scc_id[v]:
scc_out_degree[scc_id[u]] += 1
sink_count = 0
sink_scc_id = -1
for i in range(1, scc_count + 1):
if scc_out_degree[i] == 0:
sink_count += 1
sink_scc_id = i
if sink_count == 1:
print(scc_size[sink_scc_id])
else:
print(0)
if __name__ == "__main__":
main()
算法及复杂度
- 算法：强连通分量 (Tarjan 算法) + 缩点
- 时间复杂度：
。其中
是员工（顶点）数量，
是信任关系（边）数量。
- Tarjan 算法的复杂度是
- 计算缩点图的出度和 SCC 的大小需要遍历所有节点和边，复杂度也是
- 因此，总时间复杂度是线性的。
- Tarjan 算法的复杂度是
- 空间复杂度：
京公网安备 11010502036488号