题解

题面描述

在视频应用 APP 中，有多个专区，每个专区可以包含多个栏目，称为栏目的上架。专区是顶层栏目，父对象为 root，用 -1 表示。一个专区内只能包含栏目，不能包含其他专区。栏目和专区的名称互不重复，且同一栏目可以被多个不同的专区或父栏目上架。由于运营人员的误操作，可能会出现栏目之间的死循环，即在从根节点到叶子节点的遍历过程中，出现重复的栏目名称，导致系统执行代码时陷入死循环，最终引发系统宕机。题目要求设计一个程序检测系统中的所有栏目死循环，并将其路径打印出来。如果没有检测到死循环，则输出 NotFound。

思路

这道题的核心是通过图的深度优先搜索（DFS）来检测栏目的死循环。首先，将每个上架关系解析为图的邻接表形式，其中父节点指向子节点。在遍历过程中，使用DFS从根节点 -1 开始递归地探索每个路径，同时维护一个路径栈和一个访问集合，以检测路径中是否存在重复的栏目节点。如果发现重复节点，说明出现了死循环，记录当前路径并停止继续递归。最后，对所有死循环路径进行排序和去重，如果没有检测到任何死循环，输出 NotFound。

1. 输入解析：

   • 输入字符串按 ; 分割，得到多个上架关系。
   • 每个上架关系可能包含多个父关系，用 : 分割。
   • 每个父关系用 , 分割出子栏目和父栏目，构建图的邻接表（父节点到子节点的映射）。

2. 构建图：

   • 使用邻接表表示图，parent -> list of children。
   • 注意同一个子栏目可能有多个父栏目，需要处理多重父关系。

3. 检测死循环：

   • 使用深度优先搜索（DFS）从根节点 -1 开始遍历图。
   • 在 DFS 过程中，维护一个路径栈和一个访问集合，用于检测当前路径中是否有重复的节点。
   • 当遇到已经在当前路径中的节点时，表示发现一个死循环，将当前路径记录下来。

4. 记录和输出循环路径：

   • 将所有检测到的循环路径存储在一个容器中。
   • 最后，对所有路径按字典序排序，并逐行输出。
   • 如果没有检测到任何死循环，则输出 NotFound。

cpp

#include <bits/stdc++.h>
using namespace std;

// 函数：按多个分隔符分割字符串
vector<string> split(const string &s, const string &delims) {
    vector<string> tokens;
    size_t start = 0, pos;
    while ((pos = s.find_first_of(delims, start)) != string::npos) {
        if (pos > start)
            tokens.emplace_back(s.substr(start, pos - start));
        start = pos + 1;
    }
    if (start < s.length())
        tokens.emplace_back(s.substr(start));
    return tokens;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string input;
    // 读取整行输入
    getline(cin, input);
    
    // 按 ";" 和 ":" 分割输入，得到各个上架关系
    vector<string> relationships = split(input, ";:");
    
    // 构建父节点到子节点的映射关系
    unordered_map<string, vector<string>> parent_to_children;
    for(auto &rel : relationships){
        size_t comma = rel.find(',');
        if(comma == string::npos) continue; // 无效输入，但题目保证输入合法
        string child = rel.substr(0, comma);
        string parent = rel.substr(comma + 1);
        parent_to_children[parent].push_back(child);
    }
    
    vector<string> cycles; // 存储所有发现的循环路径
    // 当前路径和已访问节点集合
    vector<string> current_path;
    unordered_set<string> current_visited;
    
    // 存储所有循环路径
    vector<string> all_cycles;
    
    // 定义深度优先搜索的递归函数
    function<void(string)> dfs = [&](string node) {
        current_path.push_back(node);          // 将当前节点加入路径
        current_visited.insert(node);          // 标记当前节点为已访问
        if(parent_to_children.find(node) != parent_to_children.end()){
            for(auto &child : parent_to_children[node]){
                if(current_visited.find(child) != current_visited.end()){
                    // 发现循环，记录循环路径
                    string cycle_path;
                    for(auto &n : current_path){
                        cycle_path += n + "->";
                    }
                    cycle_path += child;
                    all_cycles.push_back(cycle_path);
                }
                else{
                    dfs(child); // 继续递归搜索子节点
                }
            }
        }
        current_path.pop_back();               // 回溯，移除当前节点
        current_visited.erase(node);           // 取消当前节点的访问标记
    };
    
    // 从根节点 "-1" 开始进行深度优先搜索
    dfs("-1");
    
    if(all_cycles.empty()){
        cout << "NotFound\n"; // 如果没有发现任何循环，输出 NotFound
        return 0;
    }
    
    // 按字典序对所有循环路径进行排序
    sort(all_cycles.begin(), all_cycles.end());
    
    // 输出每一条循环路径
    for(auto &cycle : all_cycles){
        cout << cycle << "\n";
    }
}

python

def split(s, delims):
    tokens = []
    start = 0
    while start < len(s):
        pos = next((i for i, char in enumerate(s[start:]) if s[start + i] in delims), -1)
        if pos == -1:
            tokens.append(s[start:])
            break
        if pos > 0:
            tokens.append(s[start:start + pos])
        start += pos + 1
    return tokens

def dfs(node, parent_to_children, all_cycles, current_path, current_visited):
    current_path.append(node)
    current_visited.add(node)
    if node in parent_to_children:
        for child in parent_to_children[node]:
            if child in current_visited:
                # 发现循环，记录循环路径
                cycle_path = "->".join(current_path) + "->" + child
                all_cycles.append(cycle_path)
            else:
                dfs(child, parent_to_children, all_cycles, current_path, current_visited)  # 继续递归搜索子节点
    current_path.pop()
    current_visited.remove(node)

def main():
    # 读取输入
    input_data = input().strip()
    
    # 按 ";" 和 ":" 分割输入，得到各个上架关系
    relationships = split(input_data, ";:")
    
    # 构建父节点到子节点的映射关系
    parent_to_children = {}
    for rel in relationships:
        comma = rel.find(',')
        if comma == -1: continue  # 无效输入，但题目保证输入合法
        child = rel[:comma]
        parent = rel[comma + 1:]
        if parent not in parent_to_children:
            parent_to_children[parent] = []
        parent_to_children[parent].append(child)
    
    # 存储所有循环路径
    all_cycles = []
    
    # 当前路径和已访问节点集合
    current_path = []
    current_visited = set()
    
    # 从根节点 "-1" 开始进行深度优先搜索
    dfs("-1", parent_to_children, all_cycles, current_path, current_visited)
    
    if not all_cycles:
        print("NotFound")  # 如果没有发现任何循环，输出 NotFound
    else:
        # 按字典序对所有循环路径进行排序
        all_cycles.sort()
        for cycle in all_cycles:
            print(cycle)

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {

    // 函数：按多个分隔符分割字符串
    public static List<String> split(String s, String delims) {
        List<String> tokens = new ArrayList<>();
        int start = 0;
        while (start < s.length()) {
            int pos = -1;
            // 查找下一个分隔符的位置
            for (int i = 0; i < delims.length(); i++) {
                int tempPos = s.indexOf(delims.charAt(i), start);
                if (tempPos != -1 && (pos == -1 || tempPos < pos)) {
                    pos = tempPos;
                }
            }
            if (pos == -1) {
                tokens.add(s.substring(start));
                break;
            }
            if (pos > start) {
                tokens.add(s.substring(start, pos));
            }
            start = pos + 1;
        }
        return tokens;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        // 按 ";" 和 ":" 分割输入，得到各个上架关系
        List<String> relationships = split(input, ";:");

        // 构建父节点到子节点的映射关系
        Map<String, List<String>> parentToChildren = new HashMap<>();
        for (String rel : relationships) {
            int comma = rel.indexOf(',');
            if (comma == -1) continue; // 无效输入，但题目保证输入合法
            String child = rel.substring(0, comma);
            String parent = rel.substring(comma + 1);
            parentToChildren.computeIfAbsent(parent, k -> new ArrayList<>()).add(child);
        }

        // 存储所有循环路径
        List<String> allCycles = new ArrayList<>();

        // 当前路径和已访问节点集合
        List<String> currentPath = new ArrayList<>();
        Set<String> currentVisited = new HashSet<>();

        // 定义深度优先搜索的递归函数
        dfs("-1", parentToChildren, allCycles, currentPath, currentVisited);

        if (allCycles.isEmpty()) {
            System.out.println("NotFound"); // 如果没有发现任何循环，输出 NotFound
        } else {
            // 按字典序对所有循环路径进行排序
            Collections.sort(allCycles);
            for (String cycle : allCycles) {
                System.out.println(cycle);
            }
        }
    }

    public static void dfs(String node, Map<String, List<String>> parentToChildren,
                           List<String> allCycles, List<String> currentPath, Set<String> currentVisited) {
        currentPath.add(node);
        currentVisited.add(node);
        if (parentToChildren.containsKey(node)) {
            for (String child : parentToChildren.get(node)) {
                if (currentVisited.contains(child)) {
                    // 发现循环，记录循环路径
                    StringBuilder cyclePath = new StringBuilder();
                    for (String n : currentPath) {
                        cyclePath.append(n).append("->");
                    }
                    cyclePath.append(child);
                    allCycles.add(cyclePath.toString());
                } else {
                    dfs(child, parentToChildren, allCycles, currentPath, currentVisited); // 继续递归搜索子节点
                }
            }
        }
        currentPath.remove(currentPath.size() - 1);
        currentVisited.remove(node);
    }
}

题目内容

视频 $APP$ 里有多个专区，将栏目放到专区里成放到它栏目里，我们称为栏目的上架。专区是一种顶层栏目，里面只能放入栏目不能放入专区。专区的父对象就是 $root$ ，我们用 $-1$ 表示。栏目或专区里上架的栏目不能重名,所有专区不重名，也不存在栏目和专区重名，但同一个栏目可以上架到多个不同的专区或父栏目中。有时运营人员的误操作，会出现栏目的死循环。如果从栏目树的根节点往一个叶子节点遍历过程中，出现重复的栏目名称，则定义为一个栏目死循环。已知专区名称和栏目名称不会重复，且一条从根往叶子遍历的路径上最多只有一个死循坏。

如上图，有 $2$ 处出现死循环，这种栏目上架死循环的数据会导致执行代码的死循环，引发系统宕机。因此为了避免出现这种情况，需要检测系统中的栏目死循坏。现在需要设计一个栏目树死循环检测程序，将检测到的所有死循环打印出来。

如上图，有$2$处出现死循环，这种栏目上架死循环的数据会导致执行代码的死循环，引发系统宕机。因此为了避免出现这种情况，需要检测系统中的栏目死循环。现在需要设计一个栏目树死循环检测程序，将检测到的所有死循环打印出来。

输入描述

输入是一行字符串，用分号;分隔多个栏目或专区上架关系。分号分隔后每一部分为逗号分隔的字符串，逗号左边是当前栏目或专区，逗号右边为要上架的父栏目或专区。图上的输入对应为

$C1,-1;C2,-1;A,C1;B,C1;M,C2;N,C2;$$L,C2;A1,A;A2,A;A,N;A,A2;C,A2$

输入分号的数量 $<1000$ ,逗号数量 $>=1$ ，所有输入都是合法输入，没有空白字符。输入字符串长度 $<=100000$.

输出描述

从根节点 $-1$ 开始的包含死循环的路径，例如上图打印输出

$-1->C1->A->A2->A$

$-1>C2->N->A->A2->A$

多条找到的路径，打印顺序按每条路径的 $String$ 字典升序输出

每个专区下可能有多个死循环，每条找到的路径打印一行记录，如果所有专区都没有找到死循环，则最终打印

$NotFound$

样例1

输入

C1,-1;C2,-1;A,C1;B,C1;M,C2;N,C2;L,C2;A1,A;A2,A;A,N;A,A2;C,A2

输出

-1->C1->A->A2->A
-1->C2->N->A->A2->A

说明

如题目描述，这里有 $2$ 处死循环。如果一个本身有死循环的子树挂载到多个不同的节点上，则被挂载节点就会各自出现一个死循环。

样例2

输入

C1,-1;A,C1;A,A

输出

-1->C1->A->A

说明

这里栏目A里放入了自己，也是一种死循环

样例3

输入

C1,-1;A,C1;B,C1

输出

NotFound

说明

上图没有栏目死循环，故输出NotFound

提示

所有的栏目的祖先都是根节点，也就是向父节点遍历最终都可以遍历到$-1$。

在从根节点往叶子节点遍历过程中，出现死循环换后的栏目没有子栏目了。