解題區/解題區 - UVa

UVa 1364 - Knights of the Round Table

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

圓桌武士要圍一桌，由於騎士很多，他們彼此憎恨的關係也越來越複雜，梅林被聘請來計劃會議的圓桌位置，騎士們的座位必須符合下列條件，否則將會無法開會。

  • 彼此憎恨的騎士不可相鄰
  • 圓桌要恰好奇數個人，否則無法進行投票

由於是圓桌，每個騎士都恰好有兩個鄰居，梅林只想知道誰絕對沒有辦法參與圓桌，求出絕對無法參與圓桌會議的騎士個數，並不用最大化圓桌的最大人數。

Sample Input

1
2
3
4
5
6
7
5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output

1
2

Solution

首先，一個簡單的特性，二分圖如果存在環，則保證沒有奇環，因為從 X 集合出去到 Y 集合，再回到 X 集合，保證環的路徑一定經過偶數條邊。同時，存在奇環的圖，一定不是二分圖。

二分圖不存在奇環，存在奇環的圖一定不是二分圖

藉由這個道理，這題還需要點特性，如果這張圖存在奇環，對於一個 BCC (雙向連通元件)，則滿足所有點都可以在一個奇環上。有可能一個點同時在奇環或者是偶環。

這個證明也很簡單，BCC 在元件中，定義拿走任一條邊 e(u, v)，u 和 v 之間仍然存在一條路徑。那麼可以知道對於一個奇環上的點 x 和 y，以及奇環外一點 u，若 e(x, u) 存在，則 e(u, y) 也存在，則會產生兩個環，其中一個環一定是奇數。擴散下去，所有在 BCC 元件的點，都會在一個奇環上。

BCC 存在奇環，每一個點都至少在一個奇環上

很久沒寫 BCC，一直以來寫 cut point (關節點) 和 cut edge (bridge) 的機會比較高，都忘了 BCC 的寫法。一張圖，拆成 BCC 時，每一個節點可能存在數個 BCC 元件中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// BCC
#include <stdio.h> 
#include <string.h>
#include <vector> 
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1024;
class BCC {
public:
    vector<int> g[MAXN], bcc[MAXN];
    stack< pair<int, int> > stk;
    int n;
    int vfind[MAXN], findIdx;
    int visited[MAXN];
    int bcc_tmp[MAXN], bccCnt, cutPt[MAXN];
    int dfs(int u, int p) {
        visited[u] = 1;
        vfind[u] = ++findIdx;
        
        int mn = vfind[u], branch = 0, t;
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!visited[v]) {
                stk.push(make_pair(u, v));
                t = dfs(v, u);
                mn = min(mn, t), branch++;
                if (t >= vfind[u]) {
                    pair<int, int> e;
                    bcc[++bccCnt].clear();
                    do {
                        e = stk.top(), stk.pop();
                        if (bcc_tmp[e.first] != bccCnt)
                            bcc[bccCnt].push_back(e.first), bcc_tmp[e.first] = bccCnt;
                        if (bcc_tmp[e.second] != bccCnt)
                            bcc[bccCnt].push_back(e.second), bcc_tmp[e.second] = bccCnt;
                    } while (e != make_pair(u, v));
                    cutPt[u] = 1;
                }
            } else if (vfind[v] < vfind[u] && v != p) {
                stk.push(make_pair(u, v));
                mn = min(mn, vfind[v]);
            }
        }
        if (p < 0 && branch == 1)	cutPt[u] = 0;
        return mn;
    }
    void findBCC() {
        while (!stk.empty())	stk.pop();
        memset(visited, 0, sizeof(visited));
        memset(bcc_tmp, 0, sizeof(bcc_tmp));
        bccCnt = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                findIdx = 0;
                dfs(i, -1);
            }
        }
    }
    void addEdge(int x, int y) {
        g[x].push_back(y), g[y].push_back(x);
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < n; i++)
            g[i].clear();
    }
} g;
int A[MAXN][MAXN];
int belong[MAXN], color[MAXN];
int isBipartite(int u) {
    for (int i = 0; i < g.g[u].size(); i++) {
        int v = g.g[u][i];
        if (belong[u] != belong[v])	
            continue;
        if (color[v] == color[u])
            return false;
        if (!color[v]) {
            color[v] = 3 - color[u];
            if (!isBipartite(v))
                return false;
        }
    }
    return true;
}
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2 && n) {
        memset(A, 0, sizeof(A));
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y), x--, y--;
            A[x][y] = A[y][x] = 1;
        }
        
        g.init(n);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!A[i][j]) {
                    g.addEdge(i, j);
//					printf("%d %d --\n", i, j);
                }
            }
        }
        
        g.findBCC();
        
        memset(belong, 0, sizeof(belong));
        int onOddCycle[MAXN] = {};
        for (int i = 1; i <= g.bccCnt; i++) {
            for (int j = 0; j < g.bcc[i].size(); j++) {
                belong[g.bcc[i][j]] = i, color[g.bcc[i][j]] = 0;
//				printf("%d ", g.bcc[i][j]);
            }
//			puts("");
            memset(color, 0, sizeof(color));
            color[g.bcc[i][0]] = 1;
            if (!isBipartite(g.bcc[i][0])) { // 
                for (int j = 0; j < g.bcc[i].size(); j++)
                    onOddCycle[g.bcc[i][j]] = 1;
            }
        }
        
        int ret = n;
        for (int i = 0; i < n; i++)
            ret -= onOddCycle[i];
        printf("%d\n", ret);
    }
    return 0;
}
/*
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
4 5
1 2
2 3
3 4
4 1
2 4
4 4
1 2
2 3
3 1
1 4
5 5
1 4
1 5
2 5
3 4
4 5
12 3
8 7
2 3
4 2
7 12
4 7
5 6
1 7
2 1
1 3
2 7
5 1
6 3
6 7
3 7
3 4
4 1
0 0
*/