[USACO21DEC] Paired Up G

**Paired Up G**

**USACO2021 December Contest**

**Problem Statement:**

You are given a set of $n$ people, each with a unique integer ID from $1$ to $n$. Each person has a pair preference list, which is a list of their top-$k$ preferred pairs. The length of the list is at most $k$, and it contains only integers between $1$ and $n-1$. For example, if a person's ID is $5$, they might prefer to be paired with people with IDs $3$ and $2$.

Your task is to find the maximum number of pairs that can be formed such that each pair consists of two people who are both on each other's preference lists. Note that it is not allowed for a person to be paired with someone who is already paired, so once a person is paired, they cannot be paired again.

**Input:**

* The first line contains an integer $n$, which represents the number of people.
* Each of the next $n$ lines contains a list of integers representing each person's preference list. The length of this list will not exceed $k$.

**Output:**

* Output the maximum number of pairs that can be formed.

**Constraints:**

* $1 le n le2cdot10^5$
* $0 le k le100$

**Code:**

cpp#include <iostream>
#include <vector>

using namespace std;

const int N =200005;
int n, k;
vector<int> pref[N];

bool cmp(int a, int b) {
 return pref[a].size() > pref[b].size();
}

struct Pair {
 int first, second;
};

Pair pairs[N];
int ans;

void dfs(int u, bool vis[]) {
 if (vis[u]) return;
 vis[u] = true;
 for (auto v : pref[u]) {
 if (!vis[v]) {
 dfs(v, vis);
 pairs[++ans].first = u;
 pairs[ans].second = v;
 }
 }
}

int main() {
 cin >> n;
 for (int i =1; i <= n; ++i) {
 pref[i].resize(k);
 for (auto &x : pref[i]) cin >> x;
 }

 sort(pref +1, pref + n +1, cmp);

 bool vis[n +1] = {false};
 ans =0;

 for (int i =1; i <= n; ++i) {
 if (!vis[i]) dfs(i, vis);
 }

 cout << ans /2 << endl;
 return0;
}

**Explanation:**

This code uses a greedy approach to solve the problem. The idea is to sort the people based on the length of their preference lists in descending order. Then, for each person, we try to pair them with someone who is also on their preference list and has not been paired yet.

The `cmp` function is used to compare two people's preference lists. If one person's list is longer than another's, they are considered "better" and will be placed before the other in the sorted array.

The `dfs` function is a recursive function that performs a depth-first search on the graph of paired people. It takes an integer `u` as input and marks it as visited by setting `vis[u] = true`. Then, for each person `v` who is on `u`'s preference list and has not been visited yet, we recursively call `dfs(v)`.

The `pairs` array stores the pairs of people that have been formed. The `ans` variable keeps track of the number of pairs that can be formed.

Finally, we output the maximum number of pairs that can be formed by dividing `ans` by2 and printing it out.

Note: This code assumes that the input is well-formed and does not contain any errors. In a real-world scenario, you would need to add error handling and other features to make it more robust.