题解

题目概述

在软件开发中，头文件之间可能存在循环依赖的问题。例如，a.h 包含 b.h，b.h 包含 c.h，而 c.h 又包含 a.h，这样就形成了一个循环依赖。循环依赖的缺点在于，任意一个头文件的修改都会导致所有相关的头文件需要重新编译，极大地降低了开发效率。为了解决这个问题，现需要开发一个工具来检测头文件是否存在循环依赖。如果存在循环依赖，则输出循环依赖环中包含的文件数量；如果不存在循环依赖，则输出 -1。

思路分析

本题要求检测头文件之间是否存在循环依赖，并计算循环依赖环中包含的文件数量。其本质是判断图中是否有环且环上有几个节点。由于题目保证至多只有一个循环依赖，因此一旦检测到一个环即可停止。

我们可以将头文件及其包含关系看作一个有向图，其中每个节点代表一个头文件，边表示包含关系。检测图中是否存在环，可以使用深度优先搜索（DFS）算法。具体步骤如下：

1. 图的构建：

   • 将每个头文件作为图的节点。
   • 如果 a.h 包含 b.h，则在图中添加一条从 a.h 指向 b.h 的有向边。

2. 环的检测：

   • 使用DFS遍历图，记录每个节点的访问状态：
     • 0：未访问
     • 1：正在访问（在递归栈中）
     • 2：已访问
   • 在DFS过程中，如果遇到一个正在访问的节点，说明存在一个环。
   • 记录环中所有的节点，计算其数量。

3. 结果输出：

   • 如果检测到环，输出环中节点的数量。
   • 如果没有检测到环，输出 -1。

代码

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <algorithm>

using namespace std;

// 邻接表表示的图
unordered_map<string, vector<string>> graph;
// 记录节点的访问状态
unordered_map<string, int> visited; // 0: 未访问, 1: 访问中, 2: 已访问
// 存储环中的节点
unordered_set<string> cycle_nodes;
// 标记是否存在环
bool has_cycle = false;
// 路径栈，用于记录当前DFS路径
vector<string> path;

// 深度优先搜索函数
void dfs(const string& node) {
    if (has_cycle) {
        return; // 已经检测到循环，停止进一步的DFS
    }

    visited[node] = 1; // 标记为访问中
    path.push_back(node); // 将当前节点加入路径

    for (const string& neighbor : graph[node]) {
        if (visited[neighbor] == 0) {
            dfs(neighbor);
            if (has_cycle) {
                return; // 已经检测到循环，停止进一步的DFS
            }
        } else if (visited[neighbor] == 1) {
            // 发现环
            has_cycle = true;
            // 找到循环的起始位置
            auto it = find(path.begin(), path.end(), neighbor);
            if (it != path.end()) {
                // 仅添加循环中的节点
                for (; it != path.end(); ++it) {
                    cycle_nodes.insert(*it);
                }
            }
            return;
        }
    }

    path.pop_back(); // 当前节点的DFS完成，移出路径
    visited[node] = 2; // 标记为已访问
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    cin.ignore(); // 读取换行符

    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        if (line.empty()) continue;

        size_t pos = 0;
        vector<string> tokens;
        while ((pos = line.find(' ')) != string::npos) {
            tokens.push_back(line.substr(0, pos));
            line.erase(0, pos + 1);
        }
        tokens.push_back(line); // 添加最后一个token

        string file = tokens[0];
        tokens.erase(tokens.begin()); // 移除文件名
        graph[file] = tokens;
    }

    for (const auto& pair : graph) {
        const string& node = pair.first;
        if (visited[node] == 0) {
            dfs(node);
            if (has_cycle) {
                break;
            }
        }
    }

    if (has_cycle) {
        cout << cycle_nodes.size() << "\n";
    } else {
        cout << "-1\n";
    }

    return 0;
}

python

# 建立图的数据结构
graph = {}
visited = {}  # 0: 未访问, 1: 访问中, 2: 已访问
cycle_nodes = set()
has_cycle = False
path = []

def dfs(node):
    global has_cycle
    if has_cycle:
        return
    visited[node] = 1  # 标记为访问中
    path.append(node)   # 将当前节点加入路径
    for neighbor in graph.get(node, []):
        if visited.get(neighbor, 0) == 0:
            dfs(neighbor)
            if has_cycle:
                return
        elif visited.get(neighbor, 0) == 1:
            # 发现环
            has_cycle = True
            try:
                idx = path.index(neighbor)
                cycle_nodes.update(path[idx:])  # 仅添加循环中的节点
            except ValueError:
                # 理论上不会发生，因为 neighbor 应该在 path 中
                pass
            return
    path.pop()           # 当前节点的DFS完成，移出路径
    visited[node] = 2    # 标记为已访问

def main():
    import sys
    global has_cycle, cycle_nodes, graph, visited, path

    try:
        n = int(input())
    except:
        print(-1)
        return

    for _ in range(n):
        try:
            line = input().strip()
        except EOFError:
            break
        if not line:
            continue
        parts = line.split()
        file = parts[0]
        includes = parts[1:]
        graph[file] = includes

    for node in graph:
        if visited.get(node, 0) == 0:
            dfs(node)
            if has_cycle:
                break

    if has_cycle:
        print(len(cycle_nodes))
    else:
        print(-1)

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    static Map<String, List<String>> graph = new HashMap<>();
    static Map<String, Integer> visited = new HashMap<>(); // 0: 未访问, 1: 访问中, 2: 已访问
    static Set<String> cycleNodes = new HashSet<>();
    static boolean hasCycle = false;
    static List<String> path = new ArrayList<>(); // 用于记录当前DFS路径

    static void dfs(String node) {
        if (hasCycle) {
            return; // 已经检测到循环，停止进一步的DFS
        }
        visited.put(node, 1); // 标记为访问中
        path.add(node);       // 将当前节点加入路径

        for (String neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (visited.getOrDefault(neighbor, 0) == 0) {
                dfs(neighbor);
                if (hasCycle) {
                    cycleNodes.add(node); // 当前节点也属于循环的一部分
                    return;
                }
            } else if (visited.getOrDefault(neighbor, 0) == 1) {
                // 发现环
                hasCycle = true;
                int idx = path.indexOf(neighbor);
                if (idx != -1) {
                    cycleNodes.addAll(path.subList(idx, path.size()));
                }
                return;
            }
        }

        path.remove(path.size() - 1); // 当前节点的DFS完成，移出路径
        visited.put(node, 2);          // 标记为已访问
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = 0;
        if (scanner.hasNextInt()) {
            n = scanner.nextInt();
            scanner.nextLine(); // 读取换行符
        }

        for (int i = 0; i < n; i++) {
            if (!scanner.hasNextLine()) {
                break;
            }
            String line = scanner.nextLine().trim();
            if (line.isEmpty()) continue;
            String[] parts = line.split("\\s+");
            String file = parts[0];
            List<String> includes = new ArrayList<>();
            for (int j = 1; j < parts.length; j++) {
                includes.add(parts[j]);
            }
            graph.put(file, includes);
        }

        for (String node : graph.keySet()) {
            if (visited.getOrDefault(node, 0) == 0) {
                dfs(node);
                if (hasCycle) {
                    break;
                }
            }
        }

        if (hasCycle) {
            System.out.println(cycleNodes.size());
        } else {
            System.out.println(-1);
        }

        scanner.close();
    }
}

题目内容

头文件循环依赖，指 $a.h$ 包含 $b.h$，$b.h$ 包含 $c.h$，$c.h$ 包含 $a.h$。

头文件循环依赖的缺点是，任一头文件修改，会导致循环依赖环的所有相关文件都需要重新编译，大大降低开发效率。

现开发一个工具，用来检测头文件是否循环依赖，若有循环依赖，则给出循环依赖的环中包含的文件数量。

用例保证至多只有一个循环依赖。没有循环包含头文件，因此返回 $-1$ .

输入描述

3
a.h b.h c.h
b.h d.h
d.h a.h

第一行一个整数 $n$ ，表示记录数。

($1<=n<=1000$) 其后每一行，$a.h$ $b.h$ $c.h$，表示头文件 $a.h$ 包含了两个头文件。

输出描述

3

解释:

a.h包含b.h
b.h包含d.h
d.h包含a.h

形成一个环，环中的头文件数量为 $3$ 个: $a.h、b.h、d.h$

样例1

输入

3
a.h b.h c.h
b.h d.h
d.h a.h

输出

3

说明

$a.h$ 包含 $b.h$

$b.h$ 包含 $d.h$

$d.h$ 包含 $a.h$ 形成一个环，

环中的头文件数量为 $3$ 个: $a.h、b.h、d.h$

样例2

输入

3
a.h b.h
b.h c.hd.h e.h

输出

-1

说明

无循环调用，返回 $-1$

提示

文件名格式:

1.采用dos 8.3格式，区分大小写

2.只包含英文字母和至多一个点号分隔符