题解 | #潜在风险客户识别#

#include <iostream>
#include <vector>
#include <set>
using namespace std;

void dfs(set<int>& risk_set, const vector<pair<int,int>>& edges, 
         set<int>& visited, int current, int m) {
    // 获取当前客户的转出对象
    int target = edges[current].second;
    
    // 如果目标客户已在风险集合或已访问集合中，说明形成环
    if(risk_set.count(target) || visited.count(target)) {
        risk_set.insert(visited.begin(), visited.end());
        return;
    }
    
    // 记录当前访问的客户
    visited.insert(target);
    
    // 继续遍历下一个转账关系
    for(int i = 0; i < m; i++) {
        if(edges[i].first == target) {
            dfs(risk_set, edges, visited, i, m);
            break;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 读取转账关系
    vector<pair<int,int>> edges(m);
    for(int i = 0; i < m; i++) {
        char separator;
        cin >> edges[i].first >> separator >> edges[i].second;
    }
    
    // 识别风险客户
    set<int> risk_set;
    for(int i = 0; i < m; i++) {
        set<int> visited;
        visited.insert(edges[i].first);
        dfs(risk_set, edges, visited, i, m);
    }
    
    // 输出安全客户
    if(risk_set.size() == n) {
        cout << "None";
    } else {
        vector<int> safe_clients;
        for(int i = 1; i <= n; i++) {
            if(risk_set.count(i) == 0) {
                safe_clients.push_back(i);
            }
        }
        
        // 按格式输出
        for(int i = 0; i < safe_clients.size(); i++) {
            cout << safe_clients[i];
            if(i < safe_clients.size() - 1) cout << " ";
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    private static void dfs(Set<Integer> riskSet, List<int[]> edges,
                          Set<Integer> visited, int current, int m) {
        int target = edges.get(current)[1];
        
        if(riskSet.contains(target) || visited.contains(target)) {
            riskSet.addAll(visited);
            return;
        }
        
        visited.add(target);
        
        for(int i = 0; i < m; i++) {
            if(edges.get(i)[0] == target) {
                dfs(riskSet, edges, visited, i, m);
                break;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        List<int[]> edges = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            String[] parts = sc.next().split(",");
            edges.add(new int[]{
                Integer.parseInt(parts[0]),
                Integer.parseInt(parts[1])
            });
        }
        
        Set<Integer> riskSet = new HashSet<>();
        for(int i = 0; i < m; i++) {
            Set<Integer> visited = new HashSet<>();
            visited.add(edges.get(i)[0]);
            dfs(riskSet, edges, visited, i, m);
        }
        
        if(riskSet.size() == n) {
            System.out.println("None");
        } else {
            List<Integer> safeClients = new ArrayList<>();
            for(int i = 1; i <= n; i++) {
                if(!riskSet.contains(i)) {
                    safeClients.add(i);
                }
            }
            
            for(int i = 0; i < safeClients.size(); i++) {
                System.out.print(safeClients.get(i));
                if(i < safeClients.size() - 1) System.out.print(" ");
            }
        }
    }
}

def dfs(risk_set, edges, visited, current, m):
    target = edges[current][1]
    
    if target in risk_set or target in visited:
        risk_set.update(visited)
        return
        
    visited.add(target)
    
    for i in range(m):
        if edges[i][0] == target:
            dfs(risk_set, edges, visited, i, m)
            break

def main():
    n, m = map(int, input().split())
    
    # 读取转账关系
    edges = []
    for _ in range(m):
        src, dst = map(int, input().split(','))
        edges.append((src, dst))
    
    # 识别风险客户
    risk_set = set()
    for i in range(m):
        visited = {edges[i][0]}
        dfs(risk_set, edges, visited, i, m)
    
    # 输出安全客户
    if len(risk_set) == n:
        print("None")
    else:
        safe_clients = [i for i in range(1, n+1) if i not in risk_set]
        print(' '.join(map(str, safe_clients)))

if __name__ == "__main__":
    main()