【HDU-5971】Wrestling Match【二分图+并查集+dfs】

【HDU-5971】Wrestling Match【二分图+并查集+dfs】

#include <iostream>
#include <stack>
#include <cstring>
#include <vector>

using namespace std;

const int LIM = 1e3 + 10;
int parent[LIM];
bool vis[LIM];
vector<int> good;
vector<int> bad;
vector<int> adj[LIM];

enum {NIL = -1, GOOD, BAD};

bool dfs(int crt) {
    stack<int> s;
    s.push(crt);
    while (!s.empty()) {
        crt = s.top();
        s.pop();
        if (vis[crt]) continue;
        vis[crt] = true;
        // cout << crt << " : " << parent[crt] << endl;
        for (int i = 0; i < adj[crt].size(); i++) {
            if (parent[adj[crt][i]] == NIL) {
                parent[adj[crt][i]] = parent[crt] ^ 1;
                s.push(adj[crt][i]);
            } else if (parent[crt] + parent[adj[crt][i]] != 1) {
                return false;
            }
        }
    }
    return true;
}

bool judge(int n) {
    // use pre-acknowledge give identities to some certain persons
    for (int i = 0; i < good.size(); i++) {
        if (parent[good[i]] == NIL) {
            parent[good[i]] = GOOD;
        } else if (parent[good[i]] == BAD) {
            return false;
        }
        if (vis[i]) continue;
        if (!dfs(good[i])) return false;
    }
    for (int i = 0; i < bad.size(); i++) {
        if (parent[bad[i]] == NIL) {
            parent[bad[i]] = BAD;
        } else if (parent[bad[i]] == GOOD) {
            return false;
        }
        if (vis[i]) continue;
        if (!dfs(bad[i])) return false;
    }
    // prejudge if there are some person never join in any matchs
    for (int i = 1; i <= n; i++)
        if (parent[i] == NIL && !adj[i].size())
            return false;
    // find if there are some person doesn't have identities
    int pos = NIL;
    for (int i = 1; i <= n; i++)
        if (parent[i] == NIL) {
            pos = i;
            break;
        }
    // if everyone have the identities
    if (pos == NIL) return true;
    // give identities to one of the person who doesn't have identity
    // and try to detect if there is the contradiction
    parent[pos] = GOOD;
    if (!dfs(pos)) return false;
    // if there are still some person doesn't have identities,
    // return false
    for (int i = 1; i <= n; i++)
        if (parent[i] == NIL)
            return false;
    return true;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, x, y;
    while (cin >> n >> m >> x >> y) {
        // init
        memset(vis, false, sizeof vis);
        memset(parent, NIL, sizeof parent);
        for (int i = 1; i <= n; i++)
            adj[i].clear();
        good.clear();
        bad.clear();
        // load the adjacent map
        int u, v;
        for (int i = 0; i < m; i++) {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        // load the set
        for (int i = 0; i < x; i++) {
            cin >> u;
            good.push_back(u);
        }
        for (int i = 0; i < y; i++) {
            cin >> u;
            bad.push_back(u);
        }
        cout << (judge(n) ? "YES" : "NO") << "\n";
    }
    return 0;
}