Sponsored
Sponsored
This approach uses a Union-Find (also known as Disjoint Set Union, DSU) data structure to count the number of swaps needed to pair the couples. By treating each couple as a connected component, we can iterate through the row and connect each person to their designated partner. The number of swaps needed is equivalent to the number of components minus one.
Time Complexity: O(N), where N is the number of seats, because each union-find operation is O(1) on average using path compression and union by rank.
Space Complexity: O(N) for the parent array to store the parent of each node.
1#include <stdio.h>
2
3#define MAXN 60
4int parent[MAXN];
5
6int find(int x) {
7 if (parent[x] == x) return x;
8 return parent[x] = find(parent[x]);
9}
10
11void unionSet(int x, int y) {
12 int rootX = find(x);
13 int rootY = find(y);
14 if (rootX != rootY) parent[rootX] = rootY;
15}
16
17int minSwapsCouples(int* row, int rowSize) {
18 for (int i = 0; i < rowSize; i++) {
19 parent[i] = i;
20 }
21 for (int i = 0; i < rowSize; i += 2) {
22 int a = row[i];
23 int b = row[i + 1];
24 unionSet(a / 2, b / 2);
25 }
26 int swaps = 0;
27 for (int i = 0; i < rowSize / 2; ++i) {
28 if (find(i) == i) swaps++;
29 }
30 return swaps - 1;
31}
32
33int main() {
34 int row[] = {0, 2, 1, 3};
35 int size = sizeof(row)/sizeof(row[0]);
36 printf("Minimum swaps required: %d", minSwapsCouples(row, size));
37 return 0;
38}The code defines a union-find or disjoint set structure to manage and connect couples efficiently. Each couple's pair is connected using the union operation inside a loop of couples. Finally, we check independent sets (or components) to compute the number of swaps, with the formula `swaps = components - 1`.
This approach processes the row greedily to minimize swaps by placing each person in its correct position. Misplaced pairs turn into cycles; reducing each cycle requires one swap for each element in excess of two in the cycle. Thus, we can directly count cycles and deduce swaps.
Time Complexity: O(N), iterating the seats for correction.
Space Complexity: O(N), necessary to track positions of individuals.
1
This C solution computes individual positions of persons to navigate swaps straightforwardly by positioning partners near one another. A systematic swap reduces cycles to achieve minimized swaps.