题意:求一张图中不属于任何一个奇圈的节点的个数。
无向图中,若一个点双连通分量内有一个奇圈,可以看出改连通分量内的所有点都可以包含在一个奇圈内,所以可以用dfs求出图中的所有的点双连通分量,每求出一个连通分量,判断其是否为二分图,若为二分图则该连通分量中没有奇圈,若不是二分图,该连通分量中的所有点都不是要求的点。同时要注意一个点可以同时属于多个点双连通分量。
#include <iostream> #include <cstdio> #include <cstring> #include <stack> #include <vector> #include <algorithm> using namespace std; const int maxn = 1000 + 10; const int maxm = 1000000 + 10; struct edge { int v, next; }edges[maxm]; int n, m, edgehead[maxn], tot, pre[maxn], bccno[maxn], dfs_clock, bcc_cnt, odd[maxn], color[maxn]; int now[maxn], top, mar[maxn][maxn]; stack<int> S; void init() { memset(edgehead, 0xff, sizeof(edgehead)); memset(pre, 0, sizeof(pre)); dfs_clock = tot = bcc_cnt = 0; memset(mar, 0, sizeof(mar)); memset(odd, 0, sizeof(odd)); memset(bccno, 0, sizeof(bccno)); } void addedge(int from, int to) { edges[tot].v = to; edges[tot].next = edgehead[from]; edgehead[from] = tot++; } bool bipartite(int u, int b) { for(int i = edgehead[u]; i != -1; i = edges[i].next) { int v = edges[i].v; if(bccno[v] != b) continue; if(color[v] == color[u]) return false; if(!color[v]) { color[v] = 3 - color[u]; if(!bipartite(v, b)) return false; } } return true; } int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i = edgehead[u]; i != -1; i = edges[i].next) { int v = edges[i].v; if(!pre[v]) { S.push(v); child++; int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv >= pre[u]) { bcc_cnt++; top = 0; while(1) { int x = S.top(); bccno[x] = bcc_cnt; now[top++] = x; if(x != u) S.pop(); else break; } memset(color, 0, sizeof(color)); color[u] = 1; if(top > 2 && !bipartite(u, bcc_cnt)) while(top != 0) odd[now[--top]] = 1; } } else if(v != fa) lowu = min(lowu, pre[v]); } return lowu; } int main() { freopen("in", "r", stdin); while(~scanf("%d %d", &n, &m) && n && m) { init(); while(m--) { int a, b; scanf("%d %d", &a, &b); mar[a][b] = mar[b][a] = 1; } for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(i != j && !mar[i][j]) addedge(i, j); for(int i = 1; i <= n; ++i) { if(!pre[i]) { while(!S.empty()) S.pop(); S.push(i); dfs(i, -1); } } int res = 0; for(int i = 1; i <= n; ++i) if(!odd[i]) res++; printf("%d\n", res); } return 0; } /* 5 5 1 4 1 5 2 5 3 4 4 5 0 0 2 */