华为 · 图 · 算法编程题
华为 图 n ≤ 1e3 时限 3 秒 / 256 MB

题目描述

在基因组学研究中，基因之间的调控关系可以被抽象成一个有向图，我们称之为基因调控网络。
在这个网络中，每个节点代表一个基因，一条从基因 u 指向基因 v 的有向边表示基因 u 会激活基因 v 。
科学家们对一种被称为“协同调控模体”（Co-regulatory Motif）的特殊结构非常感兴趣。
一个协同调控模体由四个不同的基因 a, b, c, d 组成，它们需要满足以下激活关系：
1. 主调节基因 a 能够直接激活两个中间基因 b 和 d 。
2. 这两个中间基因 b 和 d 又都能直接激活同一个目标基因 c 。
简单来说，这个结构意味着存在两条从基因 a 到基因 c 的长度为 2 的不同路径，一条路径为 a → b → c ，另一条为 a → d → c 。
给定一个基因调控网络的结构，请计算该网络中总共存在多少个这样的“协同调控模体”。

输入输出

输入描述
第一行包含两个整数 n 和 m ，使用空格隔开。
n 代表基因的数量（编号从 1 到 n ）， m 代表已知的直接激活关系的数量。
接下来的 m 行，每行包含两个整数 u, v ，表示存在一条从基因 u 到基因 v 的激活关系。
数据范围： 1 ≤ n ≤ 1000 ， 0 ≤ m ≤ 10000 。
输出描述
输出一个整数，代表网络中“协同调控模体”的总数量。

样例共 1 组

样例 1
输入
24 60
1 4
1 6
1 7
2 9
2 12
2 13
2 16
2 19
2 23
3 5
4 3
4 6
4 11
4 15
4 17
4 22
5 4
5 12
6 20
6 21
7 2
7 23
8 1
8 4
8 22
9 20
9 23
10 1
10 9
10 17
10 20
11 12
12 1
12 5
12 16
14 9
14 17
14 20
14 21
15 12
16 12
16 17
17 5
17 6
17 14
18 1
19 22
19 23
20 22
21 17
21 24
22 11
22 21
23 10
23 14
23 17
23 24
24 5
24 16
24 17
输出
20

算法解析依据一般

考点：图

数据规模 n ≤ 1e3 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：m ≤ 1e4，n ≤ 1e3
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：图

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 n ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：24 60 / 1 4 / 1 6 / 1 7 / 2 9 / 2 12 / 2 13 / 2 16 / 2 19 / 2 23 / 3 5 / 4 3 / 4 6 / 4 11 / 4 15 / 4 17 / 4 22 / 5 4 / 5 12 / 6 20 / 6 21 /
  • 输出：20

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-10月22号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解