けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces 360 DIV1 A NP-Hard Problem

http://codeforces.com/contest/687/problem/A
リハビリ第一弾

問題概要

無向グラフ (頂点数 n, 枝数 m) が与えられる。
このグラフの頂点集合を互いに disjoint な 2 つの集合 A, B に分割して、
A, B がともに vertex cover となっているようにせよ。
そのようなものが存在しなければ -1 をリターンせよ。

(制約)
2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000

解法

二部グラフとなっているかどうかを判定する。
なっていれば、それぞれの頂点集合を出力する。

コード

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 210000;
vector<int> G[MAX];

int seen[MAX];
vector<int> Left, Right;

bool cannot = false;
void dfs(int v, int color) {        // 1: left, 2: right
    seen[v] = color;
    if (color == 1) Left.push_back(v);
    if (color == 2) Right.push_back(v);
    int next_color = 3 - color;
    for (int i = 0; i < G[v].size(); ++i) {
        int to = G[v][i];
        if (seen[to]) {
            if (seen[to] != next_color) {
                cannot = true;
            }
        }
        else {
            dfs(to, next_color);
        }
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i < MAX; ++i) G[i].clear();
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            --a; --b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        for (int i = 0; i < MAX; ++i) seen[i] = 0;
        Left.clear(); Right.clear();
        cannot = false;
        for (int v = 0; v < n; ++v) {
            if (seen[v]) continue;
            dfs(v, 1);
        }

        if (cannot) cout << -1 << endl;
        else {
            cout << Left.size()<< endl;
            for (int i = 0; i < Left.size(); ++i) {
                cout << Left[i] + 1;
                if (i != (int)Left.size() - 1) cout << " ";
            }
            cout << endl;
            cout << Right.size()<< endl;
            for (int i = 0; i < Right.size(); ++i) {
                cout << Right[i] + 1;
                if (i != (int)Right.size() - 1) cout << " ";
            }
            cout << endl;
        }
    }
}