Fair Share(二分图)

题目 题意：给定 m m m个数组，每个数组长度 n i n_i ni​均为偶数，现将这n个数组分配到两个重复集合 L , R L,R L,R中。要求： 集合 L , R L,R L,R完全相同； 每个数组分配到集合 L , R L,R L,R数量相同。 如果存在，输出YES，并输出每个数组每个元素归属为 L L L还是 R R R。如果不存在，输出NO。

官方题解 构建二分图，左边有 m m m个点，表示 m m m个数组。右边有 ∑ n i \sum_{}^{}n_i ∑​ni​个点（去重后就没有这么多了）。如果右边每个点，出现的次数都为偶数，则有解，否则无解。

当右边每个点出现的次数都为偶数时，说明共有偶数条边。我们可以通过dfs，让左边每个点的出度和入度相等；同时让右边每个点的出度和入度相等。通过保证左边每个点的出度和入度相同，保证每个数组对于 L , R L,R L,R的贡献个数相同；通过保证右边每个点的出度和入度相同，保证集合 L , R L,R L,R中每种元素的个数相同。 我们可以让左边连右边的边取L，右边连左边的边，取L

官方代码

#include 

#define len(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"

using namespace std;

const int N = 4e5 + 100, H = 2e5 + 50;
vector  g[N];
string ans[N];
int pos[N];


void dfs(int v) {
    if (pos[v] == 0) {
        ans[v] = string(len(g[v]), 'L');
    }

    while (pos[v] i这条边标记为访问，也要将i->v标记为访问 
        g[i][ind].first = -1, g[v][pos[v]].first = -1;
        if (v > m;
    map  ind, cnt;
    int fre_ind = 0;

    vector  nums(m);
    for (int i = 0; i > n;
        for (int _ = 0; _ > x;
            if (!ind.count(x)) {
                ind[x] = fre_ind++;
            }
            x = ind[x];// 通过ind离散化 
            cnt[x]++;// cnt记录每种数的数量 
            nums[i].push_back(x);
            // 建立双向边uv，同时记录v/u对应的插入位置。 
            g[i].emplace_back(x + H, len(g[x + H]));
            g[x + H].emplace_back(i, len(g[i]) - 1);
        }
    }

    for (auto p : cnt) {
        if (p.second % 2 == 1) {
            cout