基因调控网络

题意

给定一个 个节点、 条边的有向图，统计"协同调控模体"的数量。一个协同调控模体由四个不同的节点 组成，满足：

  • ，（主调节基因 直接激活两个中间基因）
  • ，（两个中间基因都直接激活同一目标基因 ）

也就是从 到 存在两条长度为 2 的不同路径（经过不同的中间节点）。

数据范围：。

思路

先别急着枚举四元组，那样 直接起飞。换个角度想：一个模体的核心约束是什么？

固定 这对端点后，问题就变成了：有多少个中间节点 ，既是 的出邻居、又是 的入邻居？

设这样的中间节点有 个（注意 不能等于 也不能等于 ），那么从中任选 2 个作为 和 ，就得到了 个模体。

所以算法很直接：

  1. 建图的同时维护邻接矩阵（或二维数组），方便 查边。
  2. 枚举所有 对（），对于每个 ，遍历 的出邻居 ，检查 是否存在、且 、。统计满足条件的 的个数 。
  3. 累加 。

复杂度

外层枚举 是 ，内层遍历 的出邻居平均是 ，总计 。 时完全没有压力。

  • 时间：
  • 空间：（邻接矩阵）

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<int>> out(n+1);
    vector<vector<bool>> adj(n+1, vector<bool>(n+1, false));
    for(int i = 0; i < m; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        out[u].push_back(v);
        adj[u][v] = true;
    }
    long long ans = 0;
    for(int a = 1; a <= n; a++){
        for(int d = 1; d <= n; d++){
            if(a == d) continue;
            int k = 0;
            for(int x : out[a]){
                if(x != a && x != d && adj[x][d]){
                    k++;
                }
            }
            ans += (long long)k * (k - 1) / 2;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        boolean[][] adj = new boolean[n + 1][n + 1];
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i <= n; i++) out.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            out.get(u).add(v);
            adj[u][v] = true;
        }
        long ans = 0;
        for (int a = 1; a <= n; a++) {
            for (int d = 1; d <= n; d++) {
                if (a == d) continue;
                int k = 0;
                for (int x : out.get(a)) {
                    if (x != a && x != d && adj[x][d]) {
                        k++;
                    }
                }
                ans += (long) k * (k - 1) / 2;
            }
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    out = [[] for _ in range(n + 1)]
    adj = [[False] * (n + 1) for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        out[u].append(v)
        adj[u][v] = True
    ans = 0
    for a in range(1, n + 1):
        for d in range(1, n + 1):
            if a == d:
                continue
            k = 0
            for x in out[a]:
                if x != a and x != d and adj[x][d]:
                    k += 1
            ans += k * (k - 1) // 2
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const out = Array.from({length: n + 1}, () => []);
    const adj = Array.from({length: n + 1}, () => new Uint8Array(n + 1));
    for (let i = 1; i <= m; i++) {
        const [u, v] = lines[i].split(' ').map(Number);
        out[u].push(v);
        adj[u][v] = 1;
    }
    let ans = 0;
    for (let a = 1; a <= n; a++) {
        for (let d = 1; d <= n; d++) {
            if (a === d) continue;
            let k = 0;
            for (const x of out[a]) {
                if (x !== a && x !== d && adj[x][d]) {
                    k++;
                }
            }
            ans += k * (k - 1) / 2;
        }
    }
    console.log(ans);
});