之前做过这个题目，现在回想起来，又有新的柑橘。
求必须出去的骑士人数。
每一个双连通分量，如果是一个奇圈，那么一定是二分图染色失败。
依次遍历每个双连通分量，但是，对于邻接表中，有一些点不是双连通分量里面的，于是要重新编号bccno，因为割点bccno只有一个值，
但是，他要多次使用，因此要重新编号bccno
#include#include #include #include #include #include using namespace std;const int maxn = 1000 + 5;int pre[maxn];bool iscut[maxn];int bccno[maxn];int dfs_clock;int bcc_cnt;vector G[maxn],bcc[maxn];struct Edge{ int u,v; Edge(int u=0,int v=0) : u(u),v(v) {}};stack S;int dfs(int u, int fa){ int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; Edge e = (Edge){u,v}; if(!pre[v]) { S.push(e); child++; int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv >= pre[u]) { iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear(); for(;;) { Edge x = S.top(); S.pop(); if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; } if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; } if(x.u == u && x.v == v) break; } } } else if(pre[v] < pre[u] && v != fa) { S.push(e); lowu = min(lowu, pre[v]); } } if(fa < 0 && child == 1) iscut[u] = 0; return lowu;}void find_bcc(int n){ memset(pre, 0, sizeof(pre)); memset(iscut, 0, sizeof(iscut)); memset(bccno, 0, sizeof(bccno)); dfs_clock = bcc_cnt = 0; for(int i = 0; i < n; i++) if(!pre[i]) dfs(i, -1);}int odd[maxn], color[maxn];bool bipartite(int u, int b){ for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; 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 A[maxn][maxn];int main(){ int n, m; while(scanf("%d%d", &n, &m) == 2 && n) { for(int i = 0; i < n; i++) G[i].clear(); memset(A, 0, sizeof(A)); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); u--; v--; A[u][v] = A[v][u] = 1; } for(int u = 0; u < n; u++) for(int v = u+1; v < n; v++) if(!A[u][v]) { G[u].push_back(v); G[v].push_back(u); } find_bcc(n); memset(odd, 0, sizeof(odd)); for(int i = 1; i <= bcc_cnt; i++) { memset(color, 0, sizeof(color)); for(int j = 0; j < bcc[i].size(); j++) bccno[bcc[i][j]] = i; int u = bcc[i][0]; color[u] = 1; if(!bipartite(u, i)) { for(int j = 0; j < bcc[i].size(); j++) odd[bcc[i][j]] = 1; } } int ans = n; for(int i = 0; i < n; i++) if(odd[i]) ans--; printf("%d\n", ans); } return 0;}