首页 > 代码库 > POJ 2942 Knights of the Round Table （点-双连通分量 + 交叉法染色判二分图）
POJ 2942 Knights of the Round Table （点-双连通分量 + 交叉法染色判二分图）
POJ 2942 Knights of the Round Table
链接：http://poj.org/problem?id=2942
题意：亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问有多少个骑士一次会议都不能参加
1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问有多少个骑士一次会议都不能参加
思路：
1. 首先建立一张图，将憎恨关系标记下来，然后求其补图（点相同，所有的边为原图中不存在的边）。之后可以发现，如果有一个环，且其中骑士的个数为奇数个，那么这些骑士一定可以参加一次会议。
2. 如何求环，问题就转化为求点-双连通分量。接下来需要判断该双连通分量是否一定是奇圈。
3. 二分图一定不是奇圈，判断是否是二分图可以用交叉染色法求得。
4. 如果一个点-双连通分量不是二分图，那么其中一定有一个奇圈存在，但是该双连通分量中的所有点是否都符合条件呢？
5. 假如有一个奇圈存在，同时还有一个不在环中的点v，那么根据双连通分量的定义可以知道，v到该环一定有两条路径，且环内与v相连的两点之间的路径中，一条点的个数为奇数，一条点的个数为偶数。所以加入v之后，一定能够有奇圈存在。
代码：
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 1100;
int vis[maxn], bccno[maxn], dfn[maxn], low[maxn], cnt, n, m; //其中割点的bccno[]无意义
vector<int> g[maxn], bcc[maxn];
struct edge {
int u, v;
edge(int _u, int _v) {
u = _u, v = _v;
}
};
stack<edge> s;
void dfs(int u, int f, int dep) {
vis[u] = 1;
low[u] = dfn[u] = dep;
int child = 0;
for (int i = 0; i < g[u].size(); i++) if (g[u][i] != f) {
int v = g[u][i];
edge e(u, v);
if (vis[v] == 2) continue;
s.push(e);
if (vis[v] == 1 && dfn[v] < low[u]) low[u] = dfn[v];
if (vis[v] == 0) {
dfs(v, u, dep + 1);
child++;
if (low[v] < low[u]) low[u] = low[v];
if (low[v] >= dfn[u]) {
cnt++;
bcc[cnt].clear(); //cnt从1开始！
while(1) {
edge x = s.top();
s.pop();
if (bccno[x.u] != cnt) bcc[cnt].push_back(x.u), bccno[x.u] = cnt; //这里存的是每个点-双连通分量里的点(如果要存边需要修改）
if (bccno[x.v] != cnt) bcc[cnt].push_back(x.v), bccno[x.v] = cnt;
if (x.u == u && x.v == v) break;
}
}
}
}
vis[u] = 2;
}
void find_bcc(int n) {
memset(vis, 0, sizeof(vis));
memset(bccno, 0, sizeof(bccno));
while(!s.empty()) s.pop();
cnt = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i, -1, 0);
}
int mp[maxn][maxn], odd[maxn], color[maxn];
bool bipartite(int u, int id) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (bccno[v] != id) continue;
if (color[u] == color[v]) return false;
if (!color[v]) {
color[v] = 3 - color[u];
if (!bipartite(v, id)) return false;
}
}
return true;
}
int main () {
while(~scanf("%d%d", &n, &m), n || m) {
for (int i = 0; i <= n; i++) {
g[i].clear();
for (int j = 0; j <= n; j++) mp[i][j] = 0;
}
int u, v;
while(m--) {
scanf("%d%d", &u, &v);
mp[u][v] = mp[v][u] = 1;
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (!mp[i][j]) g[i].pb(j), g[j].pb(i);
find_bcc(n);
memset(odd, 0, sizeof(odd));
for (int i = 1; i <= 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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。