UVALive3523-Knights of the Round Table(BCC+二分图判定)
来源：程序员人生 发布时间：2014-10-04 08:00:00 阅读次数：3363次
题目链接
题意：有n个骑士经常举行圆桌会议，每次至少3人参加，且相互厌恶的其实不能坐在圆桌相邻的位置。如果发生意见分歧，则要举手表决，因此参加的骑士数目一定要为奇数。统计有多少人不能参加任何一个会议。
思路：这是大白上面的一道例题。我们可以先根据骑士之间的关系建立无向图G，则题目就转化为求不再任何一个简单奇圈上的结点个数。如果图G不连通，就分别对G的连通分量求解。简单圈上的所有结点必然属于同一个双连通分量，因此我们只要求出所有的双连通分量。但是二分图是不存在奇圈的，所以我们只需要关注那些不是二分图的双连通分量。当结点v所属的某一个双连通分量B不是二分图，v一定属于一个奇圈。所以我们只要判断双连通分量是不是二分图就可以了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1050;
struct edge{
edge() {}
edge(int uu, int vv) {
u = uu;
v = vv;
}
int u, v;
};
vector<int> g[MAXN], bcc[MAXN];
stack<edge> S;
int pre[MAXN], bccno[MAXN], iscut[MAXN], odd[MAXN], color[MAXN], map[MAXN][MAXN];
int n, m, dfs_clock, bcc_cnt;
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(u, v);
if (!pre[v]) {
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if (lowv >= pre[u]) {
iscut[u] = 1;
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() {
memset(pre, 0, sizeof(pre));
memset(bccno, 0, sizeof(bccno));
memset(iscut, 0, sizeof(iscut));
dfs_clock = bcc_cnt = 0;
for (int i = 0; i < n; i++)
if (!pre[i])
dfs(i, -1);
}
int bipartite(int u, int cur_bccno) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (bccno[v] != cur_bccno) continue;
if (color[v] == color[u]) return 0;
if (!color[v]) {
color[v] = 3 - color[u];
if (!bipartite(v, cur_bccno)) return 0;
}
}
return 1;
}
int main() {
while (scanf("%d%d", &n, &m) && (n + m)) {
for (int i = 0; i < n; i++) g[i].clear();
memset(map, 0, sizeof(map));
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
u--;
v--;
map[u][v] = map[v][u] = 1;
}
for (int i = 0; i < n; i++)
g[i].clear();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (!map[i][j]) {
g[i].push_back(j);
g[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 = 0; i < n; i++)
if (odd[i])
ans--;
printf("%d
", ans);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
