UVALive3523-Knights of the Round Table(BCC+二分圖判定)
來源：程序員人生 發(fā)布時間：2014-10-04 08:00:00 閱讀次數(shù)：3531次
題目鏈接
題意：有n個騎士經(jīng)常舉行圓桌會議，每次至少3人參加，且相互厭惡的其實不能坐在圓桌相鄰的位置。如果發(fā)生意見分歧，則要舉手表決，因此參加的騎士數(shù)目一定要為奇數(shù)。統(tǒng)計有多少人不能參加任何一個會議。
思路：這是大白上面的一道例題。我們可以先根據(jù)騎士之間的關(guān)系建立無向圖G，則題目就轉(zhuǎn)化為求不再任何一個簡單奇圈上的結(jié)點個數(shù)。如果圖G不連通，就分別對G的連通分量求解。簡單圈上的所有結(jié)點必然屬于同一個雙連通分量，因此我們只要求出所有的雙連通分量。但是二分圖是不存在奇圈的，所以我們只需要關(guān)注那些不是二分圖的雙連通分量。當(dāng)結(jié)點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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
