arrays - 最小可能数组置换问题

Question

在这个问题中，我得到了一个数组和一个二进制矩阵(仅由 0 和 1 组成的矩阵)，i 和 j 值可以被认为是数组元素的索引，如果 matrix[i][j]= =1 然后我们可以交换 a[i] 和 a[j] ，现在我要做的是以任何顺序使用矩阵中的所有那些来获得最小可能的排列， 这是初始数组假设 n = 5 大小的数组在那里

4 2 1 5 3

现在这是给定的矩阵，它是nXn

00100

00011

10010

01101

01010

使用所有这些，我们可以获得像这样的最小可能排列 (使用从1开始的索引来解释)

4 2 1 5 3 初始

我们做 (p1<->p3)

我们得到，1 2 4 5 3

现在我们做 (p4<->p5)

我们得到，1 2 4 3 5

现在我们做 (p3<->p4)

我们得到， 1 2 3 4 5

这是我们可以使用的最低限度的

我可以想到蛮力，但这当然会超出时间限制，所以我想知道如何以更好的方式解决这个问题。

有关更多详细信息，这是问题的链接，https://www.hackerrank.com/contests/pre-placement-coding-test/challenges/smallest-permutation/problem .

Answer 1

如果您将“可能互换”矩阵解释为图形，那么您会发现，在每个 connected component 中您可以按照您想要的任何顺序重新排列数字。

因此解决方案是找到所有组件并在每个组件中独立排序数字。

# read input
n = int(input())
p = list(map(int, input().split()))
a = [list(map(int, input().strip())) for i in range(n)]


# find components
color = [None] * n
def dfs(v, cl):
    if color[v] is not None:
        return
    color[v] = cl
    for u in range(n):
        if a[v][u]:
            dfs(u, cl)

for i in range(n):
    dfs(i, i)

# sort every component
buckets = [[] for i in range(n)]
for i in range(n):
    buckets[color[i]].append(p[i])

for bucket in buckets:
    bucket.sort(reverse=True)

# build answer
print(*(buckets[color[i]].pop() for i in range(n)))