本文共 3293 字，大约阅读时间需要 10 分钟。
为了解决这个问题，我们需要证明四个关于矩阵 A 的命题是等价的。我们可以通过分析这些命题之间的关系，并利用图论中的强连通分量和有向无环图（DAG）来确定需要证明的额外边数。
import syssys.setrecursionlimit(1 << 25)def main(): import sys input = sys.stdin.read().split() ptr = 0 T = int(input[ptr]) ptr += 1 for _ in range(T): n = int(input[ptr]) m = int(input[ptr+1]) ptr +=2 adj = [[] for _ in range(4)] for __ in range(m): s1 = int(input[ptr])-1 s2 = int(input[ptr+1])-1 adj[s1].append(s2) ptr +=2 # Build reverse graph rev_adj = [[] for _ in range(4)] for u in range(4): for v in adj[u]: rev_adj[v].append(u) # First pass to compute order visited = [False]*4 dfn = [0]*4 low = [0]*4 order = [] time = 1 for u in range(4): if not visited[u]: stack = [] stack.append( (u, False) ) while stack: node, processed = stack.pop() if processed: for v in adj[node]: if dfn[v] > dfn[node]: low[node] = min(low[node], dfn[v]) if low[node] == dfn[node]: order.append(node) continue if visited[node]: continue visited[node] = True dfn[node] = time low[node] = time time +=1 stack.append( (node, True) ) for v in adj[node]: if not visited[v]: stack.append( (v, False) ) # Second pass to find components visited = [False]*4 component = [0]*4 current_component = 0 for u in reversed(order): if not visited[u]: stack = [u] visited[u] = True component[u] = current_component while stack: node = stack.pop() for v in rev_adj[node]: if not visited[v]: visited[v] = True component[v] = current_component stack.append(v) current_component +=1 # Calculate in_degree and out_degree for DAG in_degree = [0]*4 out_degree = [0]*4 for u in range(4): for v in adj[u]: out_degree[u] +=1 for v in rev_adj[u]: in_degree[v] +=1 a = sum(1 for i in range(4) if in_degree[i] == 0) b = sum(1 for i in range(4) if out_degree[i] == 0) res = max(a, b) print(res)if __name__ == "__main__": main()
该方法确保了我们能够高效地确定需要证明的最少边数，从而完成所有命题的等价性证明。
转载地址：http://nnfx.baihongyu.com/