题解：CF687A NP-Hard Problem

DragonPig · 2026-05-06 20:36:53 · 题解

题意

给定一个无向图，要求将其顶点集划分为两个不相交的子集 A 和 B（可以有顶点不属于任何集合），使得 A 和 B 都是图的一个点覆盖。

思路

显然是一道判断二分图的模板，注意图并非连通。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inl inline
#define ls (p << 1)
#define rs (p << 1 | 1)
#define Cst constexpr
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define pb(x) push_back(x)
#define SZ(x) (int)(x).size()
#define ppc(x) __builtin_popcount(x)
#define All(x) (x).begin(), (x).end()
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))

Cst int N = 1e5 + 5;
auto fIO = []() {
    return cin.tie(0)->sync_with_stdio(0), 0;
}();
int n, m, head[N], idx, col[N], cnt0, cnt1;
struct { int v, nxt; } E[N << 1];
void AddEdge(int u, int v) {
    E[++idx] = {v, head[u]};
    head[u] = idx;
}
void Bfs(int s) {
    queue<int> q;
    q.push(s), col[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = E[i].nxt) {
            int v = E[i].v;
            if (col[v] == -1) {
                col[v] = col[u] ^ 1;
                q.push(v);
            } else if (col[v] != (col[u] ^ 1)) {
                cout << -1; exit(0);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cnt0 += (col[i] == 0), cnt1 += (col[i] == 1);
    }
}
signed main() {
    mems(col, -1);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        AddEdge(u, v), AddEdge(v, u);
    }
    for (int i = 1; i <= n; ++i)
        if (col[i] == -1) Bfs(i);
    cout << cnt0 << '\n';
    for (int i = 1; i <= n; ++i)
        if (col[i] == 0) cout << i << ' ';
    cout << '\n' << cnt1 << '\n';
    for (int i = 1; i <= n; ++i)
        if (col[i] == 1) cout << i << ' ';
}

::::