题面简述

某系统有多个服务，并且服务间可能存在依赖关系。服务之间的依赖是传递性的，即如果一个服务出现故障，它依赖的服务也会受到影响。给定一个依赖关系列表和一个故障服务列表，我们需要找出所有没有故障的服务，并且要求按依赖关系中的出现顺序输出。

题解思路

1. 依赖图的构建

首先，我们可以将服务间的依赖关系看作是一个有向图，其中每个节点代表一个服务，每条边表示一个服务依赖于另一个服务。例如，服务 A 依赖服务 B 这条边表示为 A<-B。因此，我们需要用一个邻接表来表示反向依赖关系（从服务 B 到 A），即每个服务记录哪些其他服务依赖它。

2. 故障服务的影响传播

服务之间的依赖是传递性的，也就是说，如果一个服务故障，它依赖的服务也会故障。我们可以使用广度优先搜索（BFS）来传播故障服务，遍历所有与故障服务直接或间接相关的服务。

3. 保证输出顺序

最终的输出需要按依赖关系中服务出现的顺序输出。这就要求我们在输出时，按照输入的依赖关系顺序进行输出。

Python 代码实现

from collections import defaultdict, deque

def find_operational_services(dependencies, faults):
    # 创建一个反向依赖图：对于每个服务，记录哪些服务依赖它
    graph = defaultdict(list)
    services = set()  # 用来记录所有出现的服务
    for dep in dependencies:
        service1, service2 = dep.split('-')
        graph[service2].append(service1)
        services.add(service1)
        services.add(service2)
    
    # 故障服务集合
    faulty_services = set(faults)
    
    # 使用广度优先搜索或深度优先搜索标记受影响的服务
    affected_services = set(faulty_services)
    queue = deque(faulty_services)
    
    while queue:
        current_service = queue.popleft()
        # 遍历所有依赖当前服务的服务
        for dependent_service in graph[current_service]:
            if dependent_service not in affected_services:
                affected_services.add(dependent_service)
                queue.append(dependent_service)
    
    # 过滤出可能的正常服务
    operational_services = services - affected_services
    
    # 需要按输入的依赖关系出现的顺序输出
    result = []
    for dep in dependencies:
        service1, service2 = dep.split('-')
        if service1 in operational_services and service1 not in result:
            result.append(service1)
        if service2 in operational_services and service2 not in result:
            result.append(service2)
    
    return ','.join(result) if result else ','

# 输入读取
dependencies = input().strip().split(',')
faults = input().strip().split(',')

# 调用函数
print(find_operational_services(dependencies, faults))

Java 代码实现

import java.util.*;

public class Main {
    public static String findOperationalServices(String[] dependencies, String[] faults) {
        Map<String, List<String>> graph = new HashMap<>();
        Set<String> services = new HashSet<>();
        
        // 创建反向依赖图
        for (String dep : dependencies) {
            String[] parts = dep.split("-");
            String service1 = parts[0];
            String service2 = parts[1];
            graph.putIfAbsent(service2, new ArrayList<>());
            graph.get(service2).add(service1);
            services.add(service1);
            services.add(service2);
        }
        
        Set<String> faultyServices = new HashSet<>(Arrays.asList(faults));
        Set<String> affectedServices = new HashSet<>(faultyServices);
        
        Queue<String> queue = new LinkedList<>(faultyServices);

      // 使用广度优先搜索或深度优先搜索标记受影响的服务
        while (!queue.isEmpty()) {
            String currentService = queue.poll();
            for (String dependentService : graph.getOrDefault(currentService, new ArrayList<>())) {
                if (!affectedServices.contains(dependentService)) {
                    affectedServices.add(dependentService);
                    queue.add(dependentService);
                }
            }
        }
        
        // 过滤出可能的正常服务
        Set<String> operationalServices = new HashSet<>(services);
        operationalServices.removeAll(affectedServices);
        
        // 按输入依赖顺序输出
        StringBuilder result = new StringBuilder();
        for (String dep : dependencies) {
            String[] parts = dep.split("-");
            String service1 = parts[0];
            String service2 = parts[1];
            if (operationalServices.contains(service1) && result.indexOf(service1) == -1) {
                if (result.length() > 0) result.append(",");
                result.append(service1);
            }
            if (operationalServices.contains(service2) && result.indexOf(service2) == -1) {
                if (result.length() > 0) result.append(",");
                result.append(service2);
            }
        }
        
        return result.length() > 0 ? result.toString() : ",";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] dependencies = scanner.nextLine().split(",");
        String[] faults = scanner.nextLine().split(",");
        
        System.out.println(findOperationalServices(dependencies, faults));
    }
}

C++代码

#include <bits/stdc++.h>

using namespace std;

string findOperationalServices(vector<string>& dependencies, vector<string>& faults) {
    unordered_map<string, vector<string>> graph;
    unordered_set<string> services;
    
    // 创建反向依赖图
    for (int i = 0; i < (int)dependencies.size(); i += 2) {
        string service1 = dependencies[i];
        string service2 = dependencies[i + 1];
        graph[service2].push_back(service1);
        services.insert(service1);
        services.insert(service2);
    }
    
    unordered_set<string> faultyServices(faults.begin(), faults.end());
    unordered_set<string> affectedServices(faultyServices.begin(), faultyServices.end());
    
    queue<string> q;
    for (const string& fs : faultyServices) {
        q.push(fs);
    }
    
    // BFS 遍历受影响的服务
    while (!q.empty()) {
        string currentService = q.front();
        q.pop();
        for (const string& dependentService : graph[currentService]) {
            if (affectedServices.find(dependentService) == affectedServices.end()) {
                affectedServices.insert(dependentService);
                q.push(dependentService);
            }
        }
    }
    
    // 过滤出可能的正常服务
    unordered_set<string> operationalServices;
    for (const string& service : services) {
        if (affectedServices.find(service) == affectedServices.end()) {
            operationalServices.insert(service);
        }
    }
    
    // 按输入依赖顺序输出
    ostringstream result;
    unordered_set<string> addedServices;// 避免重复
    for (int i = 0; i < (int)dependencies.size(); i += 2) {
        string service1 = dependencies[i];
        string service2 = dependencies[i + 1];
        if (operationalServices.find(service1) != operationalServices.end() && addedServices.find(service1) == addedServices.end()) {
            if (!result.str().empty()) result << ',';
            result << service1;
            addedServices.insert(service1);
        }
        if (operationalServices.find(service2) != operationalServices.end() && addedServices.find(service2) == addedServices.end()) {
            if (!result.str().empty()) result << ',';
            result << service2;
            addedServices.insert(service2);
        }
    }
    
    return result.str().empty() ? "," : result.str();
}

// 分割字符串
vector<string> split(string s) {
    vector<string> rs;
    string k;
    for (char i : s) {
        if (i == '-' || i == ',') {
            rs.push_back(k);
            k.clear();
        } else {
            k += i;
        }
    }
    rs.push_back(k);
    return rs;
}

int main() {
    string line1, line2;
    vector<string> dependencies;
    vector<string> faults;
    cin >> line1;
    dependencies = split(line1);
    cin >> line2;
    faults = split(line2);
    
    cout << findOperationalServices(dependencies, faults) << endl;
    return 0;
}

题目内容

某系统中有众多服务，每个服务用字符串（只包含字母和数字，长度$<=10$）唯一标识，服务间可能有依赖关系，如 $A$ 依赖 $B$ ，则当 $B$ 故障时导致 $A$ 也故障。

依赖具有传递性，如 $A$ 依赖 $B$ ，$B$ 依赖 $C$ ，当 $C$ 故障时导致 $B$ 故障，也导致 $A$ 故障。

给出所有依赖关系，以及当前已知故障服务，要求输出所有正常服务。

依赖关系：服务 $1$ -服务 $2$ 表示“服务 $1$ ”依赖“服务 $2$ ”

不必考虑输入异常，用例保证：依赖关系列表、故障列表非空，且依赖关系数，故障服务数都不会超过$3000$ ，服务标识格式正常。

输入描述

半角逗号分隔的依赖关系列表（换行）

半角逗号分隔的故障服务列表

输出描述

依赖关系列表中提及的所有服务中可以正常工作的服务列表，用半角逗号分隔，按依赖关系列表中出现的次序排序。

特别的，没有正常节点输出单独一个半角逗号。

样例1

输入

a1-a2,a5-a6,a2-a3
a5,a2

输出

a6,a3

说明

$a1$ 依赖 $a2$，$a2$ 依赖 $a3$ ，所以 $a2$ 故障，导致 $a1$ 不可用，但不影响 $a3$ ；$a5$ 故障不影响 $a6$ 。

所以可用的是 $a3、a6$ ，在依赖关系列表中 $a6$ 先出现，所以输出:$a6,a3$。

样例2

输入

a1-a2
a2

输出

,

说明

$a1$ 依赖 $a2$ ，$a2$ 故障导致 $a1$ 也故障，没有正常节点，输出一个逗号。