题目概述
在软件开发中,头文件之间可能存在循环依赖的问题。例如,a.h 包含 b.h,b.h 包含 c.h,而 c.h 又包含 a.h,这样就形成了一个循环依赖。循环依赖的缺点在于,任意一个头文件的修改都会导致所有相关的头文件需要重新编译,极大地降低了开发效率。为了解决这个问题,现需要开发一个工具来检测头文件是否存在循环依赖。如果存在循环依赖,则输出循环依赖环中包含的文件数量;如果不存在循环依赖,则输出 -1。
思路分析
本题要求检测头文件之间是否存在循环依赖,并计算循环依赖环中包含的文件数量。其本质是判断图中是否有环且环上有几个节点。由于题目保证至多只有一个循环依赖,因此一旦检测到一个环即可停止。
在大型软件工程中,头文件之间通过包含关系建立依赖。如果存在一个文件序列 f1,f2,…,fk,其中 f1 包含 f2,f2 包含 f3,……,fk 又包含 f1,则称这些头文件形成了一个循环依赖。这样的循环会导致环内任意一个文件发生修改时,整个环上的文件都需要重新编译,降低开发效率。
现在需要实现一个检测工具。给定若干条包含关系记录,请判断这些记录是否构成循环依赖。
如果构成循环依赖,输出该循环依赖环中包含的不同头文件数量;如果没有循环依赖,输出 -1。
输入数据保证所有记录中至多只存在一个循环依赖。
每个头文件名都遵循 dos 8.3 格式,区分大小写,文件名中只包含英文字母,并且至多含有一个 . 分隔符。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册