一、问题背景
牛客17722题模拟了一个金融借贷网络，要求识别出"安全客户"——即不会陷入循环借贷的客户。这类问题在金融风控、依赖分析等领域很常见。
二、算法核心思想
图建模：将客户关系建模为有向图
拓扑排序：反向应用拓扑排序识别安全节点
出度统计：通过出度数组动态更新节点状态
三、完整代码实现（带注释）
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<int>> graph; // 邻接表存储图
vector<int> out_degree; // 出度数组
vector<bool> is_safe; // 标记是否为安全客户
void mark_safe_customers(int n) {
queue<int> q;
// 初始化：出度为0的节点是安全的
for (int i = 1; i <= n; ++i) {
if (out_degree[i] == 0) {
q.push(i);
is_safe[i] = true;
}
}
// 拓扑排序过程
while (!q.empty()) {
int u = q.front();
q.pop();
// 遍历所有指向u的节点
for (int v = 1; v <= n; ++v) {
if (find(graph[v].begin(), graph[v].end(), u) != graph[v].end()) {
out_degree[v]--;
if (out_degree[v] == 0 && !is_safe[v]) {
is_safe[v] = true;
q.push(v);
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
graph.resize(n + 1);
out_degree.resize(n + 1, 0);
is_safe.resize(n + 1, false);
// 读取边关系并构建图
for (int i = 0; i < m; ++i) {
int u, v;
char comma;
cin >> u >> comma >> v;
graph[u].push_back(v);
out_degree[u]++;
}
mark_safe_customers(n);
// 收集所有安全客户
vector<int> safe_list;
for (int i = 1; i <= n; ++i) {
if (is_safe[i]) {
safe_list.push_back(i);
}
}
// 输出结果
if (safe_list.empty()) {
cout << "None";
} else {
for (int i = 0; i < safe_list.size(); ++i) {
if (i > 0) cout << " ";
cout << safe_list[i];
}
}
return 0;
}
