UVA1364 Knights of the Round Table

​

题目链接

​ Tarjan求点双联通分量+二分图染色

​ 题中给出了不可以出现在同一个会议的骑士，但这样貌似不好写，我们可以将能够在同一会议中的骑士连边。我们可以发现在同一个奇环内的骑士一定可以开会。

​ 连完之后会形成若干个连同块，我们可以知道一个结论，只要一个强连通分量有一个奇环，那么这个强连通分量中所有点都在奇环上。如果这个强联通分量上没有奇环，那它就一定是个二分图。（反过来说也对：如果一个图为二分图，那它肯定没有奇环。）

​ 所以这道题我们可以用Tarjan求完强连通分量，然后再对每个强联同分量判断一下是否为二分图就好了。

​

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 1005;
int n, m, cnt, tag, tot, top, vcc, root;
int in[N], col[N], dfn[N], low[N], vst[N], sta[N], head[N], vis[N][N];
vector <int> d[N];
struct edge { int to, nxt; } e[N * N * 2];

void add(int x, int y) {
    e[++cnt].nxt = head[x]; head[x] = cnt; e[cnt].to = y;
}

void clear() {
    for(int i = 1;i <= n; i++) d[i].clear();
    cnt = tot = vcc = top = 0;
    memset(head, 0, sizeof(head)); memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    memset(col, 0, sizeof(col)); memset(vst, 0, sizeof(vst));
    memset(in, 0, sizeof(in));
}

void Tarjan(int x) {
    dfn[x] = low[x] = ++ tot; sta[++top] = x;
    if(x == root && !head[x]) {
        d[++vcc].push_back(x); return ;
    }
    for(int i = head[x] ; i ; i = e[i].nxt) {
        int y = e[i].to; 
        if(!dfn[y]) {
            Tarjan(y), low[x] = min(low[x], low[y]);
            if(low[y] >= dfn[x]) {
                ++vcc; int p;
                do {
                    p = sta[top--]; d[vcc].push_back(p);
                }while(p != y);
                d[vcc].push_back(x);
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

void judge(int x, int color, int now) {
    col[x] = color;
    for(int i = head[x]; i ; i = e[i].nxt) {
        int y = e[i].to;
        if(in[y] != now) continue;
        if(!col[y]) judge(y, 3 - color, now);
        else if(col[y] == color) { tag = 1; return ; }
    }
}

int main() {

    while(1) {
        n = read(); m = read(); if(!n && !m) break;
        clear();
        for(int i = 1, x, y;i <= m; i++) x = read(), y = read(), vis[x][y] = vis[y][x] = 1;
        for(int i = 1;i <= n; i++) 
            for(int j = 1;j <= n; j++) {
                if(j == i) continue;
                if(!vis[i][j]) add(i, j);
            }

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

        for(int i = 1;i <= vcc; i++) {
            for(int j = 0;j < (int)d[i].size(); j++) in[d[i][j]] = i, col[d[i][j]] = 0;
            tag = 0; 
            if(d[i].size()) judge(d[i][0], 1, i);
            if(tag) 
                for(int j = 0;j < (int)d[i].size(); j++) vst[d[i][j]] = 1;
        }

        int ans = 0;
        for(int i = 1;i <= n; i++) if(!vst[i]) ans++;
        printf("%d\n", ans);
    }

    return 0;
}