统计直接双向依赖 - 华为机试真题题解

考试平台： 时习知

分值： 200分

考试时间： 两小时（共3题）

题目描述

工具部计划开发一个代码质量检测工具,其中有一个待实现的功能是统计代码模块的直接双向依赖。

直接双向依赖是指模块之间直接互相依赖的,不统计间接依赖、传递依赖导致的双向依赖。

输入

(1)第1行只有一个数字,表示模块总数N,随后会按1到N顺序输入N行，表示1到N个模块的依赖数据。

(2)从第2行开始,每行的第1个数据表示依赖的模块数量(不会超过N)，之后的数字表示当前模块依赖的模块ID序列。该序列会按从小到大顺序输入且不会出现重复的数字。模块ID的取值一定在[1,N]之内。

(3)每行数据的数字之间的都有1个空格。

(4)模块总数N取值范围 1<=N<=2100。

输出

输出直接双向依赖的个数。

示例1

输入：
6
1 2
3 1 4 5
1 2
2 1 2
0
0

输出：
2

解释： 
输入的第一行数据6,表示共有6个模块需要分析。随后连续输入代号为1到6的模块的依赖序列。
模块1依赖模块2;
模块2依赖模块1、4、5;
模块3依赖模块2;
模块4依赖模块1、2;
模块5和6没有依赖任何模块;
其中模块1和模块2存在直接双向依赖,模块2和模块4存在直接双向依赖,一共2组。所以输出2

示例2

输入：
4
1 2
1 3
1 4
1 1

输出：
0

解释： 
输入的第一行数据4,表示共有4个模块需要分析。随后连续输入代号为1到4的模块的依赖序列。
经分析发现,模块1、2、3、4直接没有直接 的双向依赖。输出为0

题解

解题思路

1. 数据结构选择:
   • 使用二维布尔数组g[i][j]来表示模块之间的依赖关系，如果模块i依赖模块j，则g[i][j] = true。
2. 输入处理:
   • 首先读取模块数量N，然后针对每个模块读取其依赖的模块ID，并更新二维数组g。
3. 双向依赖检测:
   • 遍历二维数组，检查每一对模块i和j，如果g[i][j]和g[j][i]都为true，说明模块i和模块j之间存在直接双向依赖，计数器result增加。
4. 输出:
   • 最后输出双向依赖的计数结果。

代码复杂度

• 时间复杂度: O(N^2) ，因为我们需要遍历二维数组中所有可能的模块对。
• 空间复杂度: O(N^2) ，因为我们使用了N x N的二维布尔数组来存储依赖关系。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        
        // g[i][j] 为true 表示模块 i 依赖模块 j
        boolean[][