首页 > 代码库 > POJ 2942 Knights of the Round Table 黑白着色+点双连通分量
POJ 2942 Knights of the Round Table 黑白着色+点双连通分量
题目来源:POJ 2942 Knights of the Round Table
题意:统计多个个骑士不能參加随意一场会议 每场会议必须至少三个人 排成一个圈 而且相邻的人不能有矛盾 题目给出若干个条件表示2个人直接有矛盾
思路:求补图 能够坐在一起 就是能够相邻的人建一条边 然后假设在一个奇圈上的都是满足的 那些不再不论什么一个奇圈的就是不满足 求出全部奇圈上的点 总数减去它就是答案
首先有2个定理
1.一个点双连通分量是二分图 你就没有奇圈 假设有奇圈 那就不是二分图 充分必要条件 所以
2.一个点双连通分量有奇圈 那这个点双连通分量全部点都在奇圈上
所以这题就求点双连通分量 然后对每一个分量进行二分图判定 不是二分图 就把该双连通分量全部点都标记 标记是由于一个割点可能属于多个双连通分量
所以标记在求和
#include <vector> #include <cstdio> #include <cstring> #include <stack> #include <algorithm> using namespace std; const int maxn = 1010; struct Edge { int u, v; Edge(){} Edge(int u, int v): u(u), v(v){} }; vector <int> a[maxn]; vector <int> bcc[maxn]; int pre[maxn]; int low[maxn]; int bccno[maxn]; int dfs_clock; int bcc_cnt; int bri; int n, m; int degree[maxn]; stack <int> S; int A[maxn][maxn]; int odd[maxn]; int color[maxn]; bool bipartite(int u, int b) { for(int i = 0; i < a[u].size(); i++) { int v = a[u][i]; if(bccno[v] != b) continue; if(color[u] == color[v]) return false; if(!color[v]) { color[v] = 3 - color[u]; if(!bipartite(v, b)) return false; } } return true; } void dfs(int u, int fa) { low[u] = pre[u] = ++dfs_clock; S.push(u); for(int i = 0; i < a[u].size(); i++) { int v = a[u][i]; if(v == fa) continue; if(!pre[v]) { dfs(v, u); low[u] = min(low[u], low[v]); if(pre[u] <= low[v]) { bcc_cnt++; while(1) { int x = S.top(); S.pop(); bccno[x] = bcc_cnt; bcc[bcc_cnt].push_back(x); if(x == v) { bcc[bcc_cnt].push_back(u); break; } } } } else if(v != fa) low[u] = min(low[u], pre[v]); } /*if(low[u] == pre[u]) { bcc_cnt++; while(1) { int x = S.top(); S.pop(); bccno[x] = bcc_cnt; bcc[bcc_cnt].push_back(x); if(x == u) break; } }*/ } void find_bcc() { memset(pre, 0, sizeof(pre)); memset(bccno, 0, sizeof(bccno)); dfs_clock = bcc_cnt = bri = 0; for(int i = 1; i <= n; i++) if(!pre[i]) dfs(i, -1); } int main() { while(scanf("%d %d", &n, &m) && (n||m)) { memset(A, 0, sizeof(A)); while(m--) { int u, v; scanf("%d %d", &u, &v); A[u][v] = A[v][u] = 1; } for(int i = 0; i <= n; i++) { a[i].clear(); bcc[i].clear(); } for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++) { if(A[i][j]) continue; a[i].push_back(j); a[j].push_back(i); } find_bcc(); 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 = 1; i <= n; i++) if(odd[i]) ans--; printf("%d\n", ans); } return 0; }
POJ 2942 Knights of the Round Table 黑白着色+点双连通分量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。