[UVALive 3523]圆桌骑士 点双联通与奇环

题目大意

有N个骑士, 奇数个骑士们可以顺次坐在圆桌旁开会。
有M对骑士之间的关系不好, 关系不好的骑士不能坐在一起。
问有多少骑士永远不能参加圆桌会议。
N ≤ 1000, M ≤ 1000000

解题报告

发现自己不会点双…补了补点双的知识。
把关系良好的骑士之间连边, 那么只有不被包含在任意一个奇环内的骑士才不能参加任何圆桌会议。
首先对于一个点双, 如果它能被二染色(二分图), 那么这个点双的任意一个点都不在奇环内, 反之这个点双的任何一个点都可以被包含在至少一个奇环内。
然后这题就简单了, 求一波点双之后对每个点双判二分图即可。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
const int MAXN = 1010;
struct Node {
    int v, nxt;
} d[MAXN*MAXN*2];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
    etot ++;
    d[etot].v = b;
    d[etot].nxt = head[a];
    head[a] = etot;
}
void clear () {
    etot = 0;
    memset(head, 0, sizeof head);
}
int dfn[MAXN], low[MAXN], dfntot;
pair<int, int> stk[MAXN];
int qtot, stktop;
vector<pair<int, int> > quad[MAXN];
void tarjan (int u, int f) {
    dfn[u] = low[u] = ++dfntot;
    for(int e = head[u]; e; e = d[e].nxt) {
        if(d[e].v == f) continue ;
        if(!dfn[d[e].v]) {
            stk[++stktop] = make_pair(u, d[e].v);
            int rec = stktop;
            tarjan(d[e].v, u);
            low[u] = min(low[u], low[d[e].v]);
            if(low[d[e].v] >= dfn[u]) { // u是一枚割点! ? low[d[e].v] == dfn[d[e].v]
                qtot ++;
                quad[qtot].clear();
                while(stktop >= rec) quad[qtot].push_back(stk[stktop--]);
            }
        } else {
            low[u] = min(low[u], dfn[d[e].v]);
            if(dfn[d[e].v] < dfn[u]) // 返祖
                stk[++stktop] = make_pair(u, d[e].v);
        }
    }
    if(f == 0 && stktop) { // 两点一线, 根弹空
        qtot ++;
        quad[qtot].clear();
        while(stktop) quad[qtot].push_back(stk[stktop--]);
    }
}
bool dir[MAXN][MAXN];
int tag[MAXN], ctag;
int colr[MAXN];
bool dfs (int u, bool cur) {
    if(tag[u] != ctag) return true;
    if(colr[u] < (ctag<<1)) colr[u] = (ctag<<1)+cur;
    else {
        if(colr[u]-(ctag<<1) != cur) return false; // fail
        return true;
    }
    for(int e = head[u]; e; e = d[e].nxt)
        if(!dfs(d[e].v, !cur)) return false;
    return true;
}

bool ans[MAXN];
int main () {
    int N, M;
    while(~scanf("%d%d", &N, &M)) {
        if(N == 0 && M == 0) return 0;
        memset(dir, 0, sizeof dir);
        for(int i = 1; i<=M; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            dir[a][b] = dir[b][a] = true;
        }
        clear();
        for(int i = 1; i<=N; i++)
            for(int j = 1; j<=N; j++)
                if(i != j && !dir[i][j]) addEdge(i, j);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        dfntot = 0, qtot = 0;
        for(int i = 1; i<=N; i++)
            if(!dfn[i]) tarjan(i, 0);
        memset(tag, 0, sizeof tag);
        memset(ans, 0, sizeof ans);
        for(int i = 1; i<=qtot; i++) {
            for(int j = 0; j<(int)quad[i].size(); j++)
                tag[quad[i][j].first] = tag[quad[i][j].second] = i;
            ctag = i;
            if(!dfs(quad[i][0].first, false))
                for(int j = 0; j<(int)quad[i].size(); j++)
                    ans[quad[i][j].first] = ans[quad[i][j].second] = true;
        }
        int pans = 0;
        for(int i = 1; i<=N; i++)
            pans += !ans[i];
        printf("%d\n", pans);
    }
}