题解 | #基因调控网络#

题目链接

基因调控网络

题目描述

在一个基因调控网络（有向图）中，寻找一种名为“协同调控模体”的结构数量。

一个协同调控模体由四个不同的基因 $A, B, C, D$ 组成，它们满足以下激活关系：

主调节基因 $A$ 能直接激活两个中间基因 $B$ 和 $C$ (即存在边 $A \to B$ 和 $A \to C$ )。
这两个中间基因 $B$ 和 $C$ 又都能直接激活同一个目标基因 $D$ (即存在边 $B \to D$ 和 $C \to D$ )。

简单来说，该结构是一个“菱形”： $A \to \{B, C\} \to D$ 。

解题思路

这是一个在有向图中对特定子图进行计数的问题。暴力枚举所有四个节点的组合 ( $O(N^4)$ ) 显然会超时，我们需要一个更高效的算法。

1. 问题转换

协同调控模体的结构核心是：存在一个主调节基因 $A$ 和一个目标基因 $D$ ，并且至少有两条从 $A$ 到 $D$ 的、经过不同中间基因的、长度为 2 的路径。

例如，路径 $A \to B \to D$ 和 $A \to C \to D$ 就构成了这样一个模体。如果有三条这样的路径（例如，通过 $B, C, E$ ），则可以构成三个模体（ $(B,C)$ 组合, $(B,E)$ 组合, $(C,E)$ 组合）。

2. 高效计数算法

基于上述观察，我们可以设计一个通过计算“长度为 2 的路径”来解决问题的算法。

核心思想：遍历每一个基因，把它当作模体中的主调节基因 $A$ 。然后，对于这个固定的 $A$ ，我们去计算它能通过不同的中间基因形成多少个模体。
算法步骤：
1. 预处理：首先，根据输入构建图的邻接表 adj，其中 adj[u] 存储了所有基因 u 能直接激活的基因列表。
2. 主循环：遍历每一个基因 a (从 1 到 $N$ )，将其视为潜在的主调节基因 $A$ 。
3. 寻找两步路径：对于当前的基因 a，我们需要找到所有可以从它出发、走两步到达的基因。
  - 我们使用一个哈希表 (Map) paths2_count 来统计。paths2_count[d] 的值将记录从 a 到 d 的长度为 2 的路径有多少条。
  - 遍历 a 的所有邻居 b（即 a -> b）。
  - 再遍历 b 的所有邻居 d（即 b -> d）。
  - 每找到一条路径 a -> b -> d，我们就将 paths2_count[d] 的计数值加 1。
4. 计算组合：当遍历完 a 的所有两步可达路径后，我们检查 paths2_count 这个哈希表。
  - 对于表中的每一个条目 (d, k)，其中 k 是 paths2_count[d] 的值。
  - 这个 k 意味着，从 a 到 d 存在 $k$ 条不同的长度为 2 的路径，它们分别经过 $k$ 个不同的中间基因。
  - 从这 $k$ 个中间基因中任意选择两个，就可以与 a 和 d 构成一个协同调控模体。选择的方法数是组合数 $C(k, 2) = \frac{k \cdot (k-1)}{2}$ 。
5. 累加结果：将计算出的组合数累加到总数 total_motifs 中。
6. 循环与返回：当外层循环遍历完所有可能的基因 a 后，total_motifs 就是最终的答案。
细节：节点不同 题目要求四个基因 $A, B, C, D$ 互不相同。在我们的算法中：
- $B \neq C$ 是通过组合数 $C(k, 2)$ 保证的（从 $k$ 个不同中间基因中选两个）。
- $A \neq B, B \neq D$ 等关系在没有自环的图中是天然成立的。
- 唯一需要注意的是 $A$ 不能等于 $D$ 。因此，在找到路径 a -> b -> d 后，我们需要确保 a != d 才进行计数。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    // 使用邻接表表示图
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    long long total_motifs = 0;

    // 遍历每个基因作为主调节基因 A
    for (int a = 1; a <= n; ++a) {
        // paths2_count[d] 记录从 a 到 d 长度为2的路径数量
        map<int, int> paths2_count;

        // 遍历 A 的下游基因 B
        for (int b : adj[a]) {
            // 遍历 B 的下游基因 D
            for (int d : adj[b]) {
                // 确保 A 和 D 不同
                if (a != d) {
                    paths2_count[d]++;
                }
            }
        }

        // 计算组合数
        for (auto const& [d, k] : paths2_count) {
            if (k >= 2) {
                total_motifs += (long long)k * (k - 1) / 2;
            }
        }
    }

    cout << total_motifs << "\n";

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 使用邻接表表示图
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
        }

        long totalMotifs = 0;

        // 遍历每个基因作为主调节基因 A
        for (int a = 1; a <= n; a++) {
            // paths2Count.get(d) 记录从 a 到 d 长度为2的路径数量
            Map<Integer, Integer> paths2Count = new HashMap<>();

            // 遍历 A 的下游基因 B
            for (int b : adj.get(a)) {
                // 遍历 B 的下游基因 D
                for (int d : adj.get(b)) {
                    // 确保 A 和 D 不同
                    if (a != d) {
                        paths2Count.put(d, paths2Count.getOrDefault(d, 0) + 1);
                    }
                }
            }

            // 计算组合数
            for (int k : paths2Count.values()) {
                if (k >= 2) {
                    totalMotifs += (long) k * (k - 1) / 2;
                }
            }
        }

        System.out.println(totalMotifs);
    }
}

import collections

def main():
    n, m = map(int, input().split())

    # 使用邻接表表示图
    adj = collections.defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)

    total_motifs = 0

    # 遍历每个基因作为主调节基因 A
    for a in range(1, n + 1):
        # paths2_count[d] 记录从 a 到 d 长度为2的路径数量
        paths2_count = collections.defaultdict(int)

        # 遍历 A 的下游基因 B
        for b in adj[a]:
            # 遍历 B 的下游基因 D
            for d in adj[b]:
                # 确保 A 和 D 不同
                if a != d:
                    paths2_count[d] += 1
        
        # 计算组合数
        for k in paths2_count.values():
            if k >= 2:
                total_motifs += k * (k - 1) // 2

    print(total_motifs)

if __name__ == "__main__":
    main()

算法及复杂度

算法: 图遍历, 哈希表计数
时间复杂度: $\mathcal{O}(\sum_{(u,v) \in E} \text{out-degree}(v))$ ，其中 $E$ 是边的集合，out-degree( $v$ ) 是节点 $v$ 的出度。该复杂度的本质是遍历图中所有长度为 2 的路径，对于稀疏图而言，这远优于 $O(N^3)$ 。
空间复杂度: $\mathcal{O}(N+M)$ ，主要用于存储图的邻接表。在每次主循环中，哈希表的空间消耗最多为 $O(N)$ 。