$v_+, v_-$みたいにするのは蟻本に載ってた。

problem

単純グラフが与えられる。 この頂点を$2$つに分割せよ。特に、それぞれの頂点が頂点被覆になるように構成し出力せよ。

solution

To satisfy the required condition, it must be a bipartite graph. For this, use the union-find tree (disjoint set). $O((N + M) \alpha(N))$.

For each vertex $v$, prepare $2$ elements $v_+, v_-$. It’s $2n$ elements in total. For each edge $uv$, union the sets for $u_+, v_-$ and for $u_-, v_+$. After this merging, if $u_+$ and $v_+$ are in the same set, it means a confliction.

implementation

#include <iostream>
#include <vector>
#include <set>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

struct union_find {
    vector<int> tree;
    explicit union_find(size_t n) : tree(n, -1) {}
    bool is_root(int a) { return tree[a] < 0; }
    int find_root(int a) { return is_root(a) ? a : (tree[a] = find_root(tree[a])); }
    int tree_size(int a) { return - tree[find_root(a)]; }
    void union_tree(int a, int b) {
        a = find_root(a); b = find_root(b);
        if (a != b) {
            if (not (tree_size(a) <= tree_size(b))) swap(a,b);
            tree[b] += tree[a];
            tree[a] = b;
        }
    }
    bool is_connected(int a, int b) { return find_root(a) == find_root(b); }
};

int main() {
    // input and run
    int n, m; cin >> n >> m;
    union_find t(2*n);
    repeat (i,m) {
        int u, v; cin >> u >> v; -- u; -- v;
        t.union_tree(u, n+v);
        t.union_tree(v, n+u);
        if (t.is_connected(u, v)) {
            // output
            cout << -1 << endl;
            return 0;
        }
    }
    vector<bool> used(2*n);
    set<int> k;
    repeat (u,n) if (not used[t.find_root(u)]) {
        used[t.find_root(  u)] = true;
        used[t.find_root(n+u)] = true;
        k.insert(t.find_root(u));
    }
    vector<int> a, b;
    repeat (u,n) {
        if (k.count(t.find_root(u))) {
            a.push_back(u);
        } else {
            b.push_back(u);
        }
    }
    // output
    cout << a.size() << endl;
    repeat (i,a.size()) { if (i) cout << ' '; cout << a[i]+1; } cout << endl;
    cout << b.size() << endl;
    repeat (i,b.size()) { if (i) cout << ' '; cout << b[i]+1; } cout << endl;
    return 0;
}