python - 如何计算要更改的边数以使无向图成为单个组件？

Question

我试图用以下代码解决这个问题。但答案并不适用于所有输入。

问题陈述

Byteland 有 N 个城市和 N 个单向桥。恰好有 1 个传入和 1 个传出每个城市的桥梁。拜特兰希望获得“资格”主办世界杯。一个国家“有资格”进入世界杯赛，当且仅当您可以从任何城市前往该国的任何其他城市。你被要求执行帮助 Byteland 成为合格世界杯主办国的最少步骤。对于每一步，您都可以交换两个桥的目的地。

例如:我们有两个桥 A -> B 和C -> D (有一座从 A 到 B 和从 C 到 D 的桥)。如果我们交换他们的目的地，我们将有两个桥 A -> D 和 C -> B 。

输入格式

第一行包含一个整数，T表示测试用例的数量。每个测试都会有两行: 第一行包含一个整数 N。 第二行包含 N 个整数，其中第 X 个整数表示桥梁从城市 X 出发的城市。

输出格式

只需打印问题的答案，每个案例一行。

示例输入

2
4
3 1 2 4
3
2 3 1

示例输出

1
0

我的代码

for i in range(input()):
    n = input()
    bridges = {}
    connection = [int(y) for y in raw_input().split(' ')]
    for j in range(n):
        bridges[j+1] = connection[j]
    #print bridges
    count = 0
    swapped = True
    for k in range(1, n+1):
        if swapped:
            swapped = False
            for j in range(1, n+1):
                if bridges[bridges[j]] == j:
                    bridges[j], bridges[1 if (j+1)%n == 0 else (j+1)%n] = bridges[1 if (j+1)%n == 0 else (j+1)%n], bridges[j]
                    swapped = True
                    #print bridges
                    count += 1
    print count

Answer 1

你必须计算连通分量，那么交换的数量等于分量的数量减一。

for i in range(int(input())):
    N = int(input())
    bridges = {index + 1: int(connection) for index, connection in enumerate(input().split())}
    visited = set()
    component_count = 0
    towns = list(bridges.keys())
    while towns:
        current = towns[0]
        component = set()
        while current not in visited:
            towns.remove(current)
            visited.add(current)
            current = bridges[current]

        component_count += 1

    print(component_count - 1)

该代码执行以下操作:

• 从第一个尚未访问过的城镇开始(外环)，并沿着桥梁连接访问尽可能多的城镇(内环)
• 每次内循环中断时，都意味着我们遇到了一个我们已经遇到过的城镇，它在图中构成了一个组件。
• 中断循环并增加组件数量。从一个未被访问过的新的twon重新开始

这给出了正确的结果，因为我们保证组件是循环的，您可以打破循环(交换连接)以将一个组件连接到另一个组件而不破坏该组件。