3
Существует N целых чисел {1, 2, ..., N} и K упорядоченных пар чисел (A, B); A! = B; A, B < = N. Никакие пары не идентичны (например, (2, 4) не могут вводиться более одного раза). Один и тот же элемент может появляться во многих парах. Я должен написать программу на C++ с алгоритмом, чтобы найти число перестановок всех N целых чисел, где ни одна B из любой пары не следует за ее A. Обратите внимание, что пара (A, B)! = (B, A).Сколько перестановок N целых чисел с K пар чисел, которые не могут быть смежными?
Пример:
n = 5
k = 4
k1: (2, 3)
k2: (1, 4)
k3: (3, 2)
k4: (2, 4)
This perm. is OK: 4 1 3 5 2
This is not OK: 3 1 4 2 5
Вот моя скотина решение силы, проверяя рекурсивно все возможности:
#include <iostream>
using namespace std;
int n;
bool conflict[1000][1000];
bool visited[1000];
int result = 0;
int currentlength = 0;
void count(int a) {
visited[a] = true;
currentlength++;
if (currentlength == n) {
result++;
visited[a] = false;
currentlength--;
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i] && !conflict[a][i]) {
count(i);
}
}
visited[a] = false;
currentlength--;
}
int main()
{
int k;
cin >> n >> k;
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
conflict[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
count(i);
}
cout << result << endl;
return 0;
}
N и K идти до 1000000. и 100000 соответственно, так что мне нужно, чтобы найти более эффективное решение.
Могут пары перекрываться, например k1 = (2,3), k2 = (2,4)? –
Когда вы говорите, что пары не идентичны, вы имеете в виду, что невозможно иметь пару (1,2) и пару (1,3) на том основании, что 1 находится в обеих парах? (Или вы просто говорите, что пара (1,2) не может дважды появляться в списке?) –
Учитывая A = 1 и B = 4, я могу понять, почему «1 4» ** не ** OK. Но почему «4 1» нормально? Кажется, что B находится рядом с A для меня. Возможно, вы хотели сказать, что B не может сразу следовать A. – user3386109