「poj 2942」(点双连通分量+二分图判定)

发表于 | 分类于 | | + s

poj 2942
题意：
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的$2$个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数$n$，再给出$m$对憎恨对（表示某$2$个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议？

建补图，补图中的边即为两个骑士能一起开会议。

引理：

一个双联通分量中存在奇环，那么整个双联通分量的点一定至少被一个奇环包含。

那么本题就是在点双连通分量中求是否是奇环即可，奇环判断用二分图判定判。
容易发现二分图没有奇环，所以可以判断。

知识点：
1、点双联通分量最好记录点而不是边

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000 + 5;

    struct edge {
        int v, nxt;
    } ed[10000000 * 2 + 5];

    int n, m, gx[MAXN][MAXN], hd[MAXN], en;
    int low[MAXN], dfn[MAXN], sz;
    int vcc_num;
    int av[MAXN], col[MAXN], ok[MAXN];
    vector<int > vcc[MAXN];
    stack<int > s;

    void ins(int u, int v) {ed[++en] = (edge){v, hd[u]}, hd[u] = en;}

    void tarjan(int u, int fa) {
        dfn[u] = low[u] = ++sz, s.push(u);
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v == fa) continue ;
            if (!dfn[e.v]) {
                tarjan(e.v, u);
                low[u] = min(low[u], low[e.v]);
                if (low[e.v] >= dfn[u]) {
                    int whw; 
                    ++vcc_num;
                    do {
                        whw = s.top(); s.pop();
                        vcc[vcc_num].push_back(whw);
                    } while (whw != e.v);
                    vcc[vcc_num].push_back(u);
                }
            } else low[u] = min(low[u], dfn[e.v]);
        }
    }
    int dfs_col(int u, int fa, int c) {
        int fl = 1;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v == fa) continue ;
            if (!av[e.v]) continue ;
            if (col[e.v] == c) return false;
            if (!col[e.v]) {
                col[e.v] = 3 - c;
                int gg = dfs_col(e.v, u, 3 - c);
                if (!gg) fl = 0;
            }
        }
        return fl;
    }

    void clean() {
        ms(gx, 0), ms(hd, -1), en = -1;
        ms(low, 0), ms(dfn, 0), sz = 0;
        vcc_num = 0;
        ms(av, 0), ms(col, 0), ms(ok, 0);
        for (int i = 0; i <= n; ++i) vcc[i].clear();
    }
    int solve() {

        clean();

        for (int x, y, i = 1; i <= m; ++i) scanf("%d%d", &x, &y), gx[x][y] = gx[y][x] = 1;

        for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) if (!gx[i][j]) ins(i, j), ins(j, i);

        for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i, 0);

        /*for (int i = 1; i <= vcc_num; ++i, puts("")) 
        for (int j = 0; j < (int)vcc[i].size(); ++j) printf("%d ", vcc[i][j]);*/

        for (int i = 1; i <= vcc_num; ++i) {
            for (int j = 0; j < (int)vcc[i].size(); ++j) col[vcc[i][j]] = 0, av[vcc[i][j]] = 1;
            col[vcc[i][0]] = 1;
            int fl = dfs_col(vcc[i][0], 0, 1);
            if (!fl) for (int j = 0; j < (int)vcc[i].size(); ++j) ok[vcc[i][j]] = 1;
            for (int j = 0; j < (int)vcc[i].size(); ++j) col[vcc[i][j]] = 0, av[vcc[i][j]] = 0;
        }

        int ans = 0;
        for (int i = 1; i <= n; ++i) if (ok[i]) ++ans;

        cout << n - ans << endl;

        return 0;
    }
}
int main() {
    while (scanf("%d%d", &flyinthesky::n, &flyinthesky::m) == 2 && flyinthesky::n && flyinthesky::m) flyinthesky::solve();
    return 0;
}
------ 本文结束 ------