минимально возможная проблема перестановки массива

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 53 начальных

мы делаем (p1 <-> p3)

мы получаем, 1 2 4 5 3

теперь мы делаем (p4 <-> p5)

мы получаем, 1 2 4 3 5

и теперь мы делаем (p3 <-> p4)

получаем, 1 2 3 4 5

этоКак можно меньше, мы можем получить, используя

Я могу думать о грубой силе, но это будетКонечно, дайте TIME LIMIT EXCEEDED, поэтому мне интересно, как лучше подойти к этой проблеме.

для более подробной информации, вот ссылка на проблему, https://www.hackerrank.com/contests/pre-placement-coding-test/challenges/smallest-permutation/problem.

Answer 1

Если бы вы интерпретировали матрицу «возможных перестановок» как график, вы могли бы выяснить, что в каждом подключенном компоненте вы можете переставлять числа в любом порядке.

Итак, решениеэто найти все компоненты и отсортировать номера независимо в каждом.

# 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)))