题解 | 基因调控网络

另一种思路，相比官方解法空间复杂度更小，时间复杂度好像也更小，不知道论证的严不严谨。

先统计每个基因能激活谁和被谁激活，然后两两组合基因bd，看哪些其他基因是符合条件的a和c，最后两两组合ac基因，注意a和c不能是同一个基因。

复杂度方面，因为m << n*n，标答adj矩阵空间复杂度明显过高。时间复杂度方面，虽然本方法和标答外围两次循环都是O(n*n)，不过本方法set运算的复杂度是O(min(|set1|, |set2|))，最坏情况是m/n，总体更小一点。而且set运算由底层C语言实现。实测总体速度为标答3倍。

n, m = map(int, input().split())

activate_list = [set() for _ in range(n)]
activated_by_list = [set() for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: (int(x)-1), input().split())
    activate_list[a].add(b)
    activated_by_list[b].add(a)

# print(activate_list, activated_by_list)
count = 0
for i in range(n):
    for j in range(i+1, n):
        a_set = activated_by_list[i] & activated_by_list[j]
        if a_set:
            c_set = activate_list[i] & activate_list[j]
            if c_set:
                # print(a_set, c_set)
                count += len(a_set) * len(c_set) - len(a_set & c_set)

print(count)