牛客17722题解析：基于拓扑排序的安全客户识别算法及代码实现

一、题目解读

牛客17722题要求识别一组客户中的“安全客户”，即不存在直接或间接依赖关系的客户。题目给定n个客户和m条依赖关系（u,v表示u依赖v），需要输出所有安全客户的编号。问题本质是判断有向图中的入度为0的节点，可通过拓扑排序解决。

二、解题思路

采用拓扑排序算法。首先构建邻接表存储图，计算每个节点的出度。将出度为0的节点入队，通过拓扑排序迭代处理：每当节点出度减为0时，标记其为安全并加入队列，直至队列为空。最终输出所有安全客户编号。核心思想是利用拓扑排序的特性，逐步消除依赖关系，识别无依赖的节点。

三、解题步骤

1. 数据输入与初始化

读取n、m，构建邻接表graph，初始化出度数组out_degree和标记数组is_safe。

2. 构建图与出度计算

遍历m条边(u,v)，将v加入u的邻接表，同时out_degree[u]++。

3. 拓扑排序标记安全节点

○ 初始化队列：将出度为0的节点入队并标记为安全。

○ 迭代处理：弹出队首节点u，遍历其所有指向的节点v，将v的出度减1。若v出度减为0且未标记，则标记v为安全并入队。

4. 收集安全客户

遍历is_safe数组，收集所有标记为true的节点编号。

5. 输出结果

若安全列表为空输出"None"，否则按编号顺序输出。

四、代码及注释

#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;
}

五、总结

该代码通过拓扑排序高效解决了安全客户识别问题，时间复杂度为O(n+m)。关键点在于：

1. 利用出度数组快速定位初始安全节点；

2. 通过队列实现拓扑排序的动态更新；

3. 将实际问题转化为图论模型，凸显算法设计的巧妙性。

掌握拓扑排序的应用场景（如依赖关系、任务调度等）能提升解决类似问题的效率。