LightOJ - 1300 Odd Personality（边双连通+奇圈判定）

题目大意：给出一张无向图，要求找出符合条件的点
条件如下：从该点出发，经过一定数量的边，又回到该点，经过的边不能重复经过，且经过的边的数量为奇数

解题思路：要回到原点，且不能重复经过边，只能在边双连通分量中找了
接着要判断的是有多少个点，只要边双连通分量中有奇圈，那么这个连通分量中的所有点都是符合条件的
所以现在的问题变成了如和判断奇圈了，判断奇圈的话，用二分图染色即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
const int M = 20010;

struct Edge{
    int u, v, next;
    Edge() {}
    Edge(int u, int v, int next): u(u), v(v), next(next) {}
}E[M * 2];

int head[N], pre[N], lowlink[N], bccno[N], Stack[N], color[N], num[N];
int tot, n, m, bcc_cnt, dfs_clock, top, cas = 1;
bool vis[N];

void AddEdge(int u, int v) {
    E[tot] = Edge(u, v, head[u]);
    head[u] = tot++;
    E[tot] = Edge(v, u, head[v]);
    head[v] = tot++;
}

void init() {
    memset(head, -1, sizeof(head));
    tot = 0;

    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        AddEdge(u, v);
    }
}

void dfs(int u, int fa) {
    pre[u] = lowlink[u] = ++dfs_clock;
    Stack[++top] = u;

    for (int i = head[u]; ~i; i = E[i].next) {
        int v = E[i].v;
        if (!pre[v]) {
            dfs(v, u);
            lowlink[u] = min(lowlink[v], lowlink[u]);
            if (lowlink[v] > pre[u]) {
                int x;
                bcc_cnt++;
                num[bcc_cnt] = 0;
                while (1) {
                    x = Stack[top--];
                    bccno[x] = bcc_cnt;
                    num[bcc_cnt]++;
                    if (x == v) break;
                }
            }
        }
        else if (v != fa && pre[v] < pre[u]) lowlink[u] = min(pre[v], lowlink[u]);
    }
}

bool Bit(int u, int No) {
    for (int i = head[u]; ~i; i = E[i].next) {
        int v = E[i].v;
        if (bccno[v] != No) continue;
        if (color[v] == color[u]) return false;
        else if (color[v] + color[u] == 3) continue;
        else {
            color[v] = 3 - color[u];
            if (!Bit(v, No)) return false;
        }
    }
    return true;
}

void solve() {
    memset(pre, 0, sizeof(pre));
    memset(bccno, 0, sizeof(bccno));
    dfs_clock = top = bcc_cnt = 0;

    for (int i = 0; i < n; i++) {
        if (!pre[i]) dfs(i, -1);
        if (top != 0) {
            bcc_cnt++;
            num[bcc_cnt] = 0;
            int x;
            while (top) {
                x = Stack[top--];
                bccno[x] = bcc_cnt;
                num[bcc_cnt]++;
            }
        }
    }

    memset(vis, 0, sizeof(vis));
    memset(color, 0, sizeof(color));

    int ans = 0;
    for (int i = 0; i < n; i++) {

        int u = bccno[i];
        if (vis[u]) continue;
        vis[u] = true;
        color[i] = 1;
        if (!Bit(i, u)) ans += num[u];
    }
    printf("Case %d: %d\n", cas++, ans);
}


int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}