二分图染色

二分图

bool dfs(int u, int c) {if (color[u] == c) return true;else if (color[u] == 3 - c) return false;color[u] = c;for (int v : graph[u])if (!dfs(v, 3 - c)) return false;return true;
}

习题：P1330 封锁阳光大学

解题思路

按照题目要求，每一条边所连接的点中，至少要有一个被选中，但又不能同时选中。因此可以转化为二分图染色问题。答案取两种颜色数量较少的那个。

参考代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10005;
vector<int> graph[N];
int color[N], cnt[3];
bool dfs(int u, int c) {if (color[u] == c) return true;else if (color[u] == 3 - c) return false;color[u] = c; cnt[c]++;for (int v : graph[u])if (!dfs(v, 3 - c)) return false;return true;
}
int main()
{int n, m; scanf("%d%d", &n, &m);while (m--) {int u, v; scanf("%d%d", &u, &v);graph[u].push_back(v); graph[v].push_back(u);}bool ok = true;int ans = 0; for (int i = 1; i <= n; i++) if (color[i] == 0) {cnt[1] = cnt[2] = 0;ok &= dfs(i, 1);if (!ok) break;ans += min(cnt[1], cnt[2]);}if (!ok) printf("Impossible\n");else printf("%d\n", ans);return 0;
}

习题：CF862B Mahmoud and Ehab and the bipartiteness

解题思路

若二分图中两种点的集合的大小分别为 \(|S_1|\) 和 \(|S_2|\)，则根据二分图的定义，两种集合间的点都是可以连边的，因此最多 \(|S_1| \times |S_2|\) 条边。所以还可以添加 \(|S_1| \times |S_2| - (n - 1)\) 条边。

参考代码

#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
vector<int> graph[N];
int cnt[3], color[N];
void dfs(int u, int c) {color[u] = c; cnt[c]++;for (int v : graph[u])if (color[v] == 0) dfs(v, 3 - c); 
}
int main()
{int n; scanf("%d", &n);for (int i = 1; i < n; i++) {int u, v; scanf("%d%d", &u, &v);graph[u].push_back(v); graph[v].push_back(u);}dfs(1, 1);printf("%lld\n", 1ll * cnt[1] * cnt[2] - (n - 1));return 0;
}

习题：P6185 [NOI Online #1 提高组] 序列

解题思路

把每个位置看成一个点。

对于 \(2\) 操作，如果两个位置连通则意味着可以使一个位置 \(+1\) 而另一个位置 \(-1\)，这样一来对于整个连通块，可以使其在总和不变的情况下任意加减，因此可以用并查集将一个连通块看成一个点。

对于 \(1\) 操作连边，如果形成的图是二分图，则可以保证其两个集合内的总和之差保持不变的情况下任意加减。如果形成的图不是二分图，则可以保证整个连通块总和奇偶性保持不变的情况下任意加减。

参考代码

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 100005;
int a[N], b[N], color[N], fa[N];
LL sum[3], delta[N];
struct Operation {int t, u, v;
};  
Operation op[N];
vector<int> graph[N];
int query(int x) {return fa[x] == x ? x : fa[x] = query(fa[x]);
}
void merge(int x, int y) {int qx = query(x), qy = query(y);if (qx != qy) {fa[qx] = qy;delta[qy] += delta[qx];}
}
bool dfs(int u, int c) {if (color[u] == c) return true;else if (color[u] == 3 - c) return false;color[u] = c; sum[c] += delta[u];bool ret = true;for (int v : graph[u]) {if (!dfs(v, 3 - c)) {ret = false; // 注意这里不管是否构成二分图都要把染色流程走完}}return ret;
}
int main()
{int t; scanf("%d", &t);while (t--) {int n, m; scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);fa[i] = i; color[i] = 0;graph[i].clear();}for (int i = 1; i <= n; i++) {scanf("%d", &b[i]);delta[i] = b[i] - a[i];}for (int i = 1; i <= m; i++) {scanf("%d%d%d", &op[i].t, &op[i].u, &op[i].v);if (op[i].t == 2) {merge(op[i].u, op[i].v);}}for (int i = 1; i <= m; i++) {if (op[i].t == 1) {int qu = query(op[i].u), qv = query(op[i].v);graph[qu].push_back(qv); graph[qv].push_back(qu);}}bool ans = true;for (int i = 1; i <= n; i++) {if (color[i] == 0 && query(i) == i) {sum[1] = sum[2] = 0;bool ok = dfs(i, 1);if (ok && sum[1] != sum[2]) {ans = false; break;}// 注意坑点：C++中的负数取余if (!ok && (abs(sum[1]) + abs(sum[2])) % 2 == 1) {ans = false; break;}}}printf("%s\n", ans ? "YES" : "NO");}return 0;
}

习题：P1155 [NOIP2008 提高组] 双栈排序

解题思路

首先考虑只有一个栈的情况。用一个栈去模拟可以得到部分分（靠一个栈可以搞定的数据点以及结果为 \(0\) 的数据点）。

像 \(2 3 1\) 这个样例需要两个栈才能完成，实际上可以概括为对于 \(i < j < k\) 三个位置存在 \(a_k < a_i < a_j\)，此时 \(a_i\) 和 \(a_j\) 无法共存在同一个栈中。因为 \(a_k\) 需要在 \(a_i\) 与 \(a_j\) 之前出栈，但 \(a_i\) 又需要再 \(a_j\) 之前出栈，产生了矛盾。

因此可以预处理每个数之后最小的数，这样就可以在 \(O(n^2)\) 的时间复杂度下完成每一对 \((i,j)\) 能否共存在一个栈中的判断。

对于不能共存的两个数，实际上就需要尝试交给两个栈分别处理，则问题被转化为二分图染色问题。对于每一对不能共存的 \(i\) 和 \(j\) 连边，如果不存在合法的染色方案，则说明无解。

接下来考虑如何保证字典序最小：

染色时让编号小的数尽量放入第一个栈，最终每个点的染色方案代表其交给哪一个栈来处理。用两个栈模拟操作时，注意如果第二个栈的栈顶是下一个排完序的数时，不一定马上就将其出栈（d 操作），此时有一部分 a 操作可以先引入进来（字典序更小），而这时可行的 a 操作需要保证新入栈的数属于第一个栈并且小于第一个栈的栈顶（否则说明它至少要等当前的栈顶出栈之后才能入栈）。

参考代码

#include <cstdio>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
const int N = 1005;
int n, a[N], color[N], ans[N * 2], suf[N], g[N][N];
bool dfs(int u, int c) {if (color[u] == c) return true;else if (color[u] == 3 - c) return false;color[u] = c;for (int i = 1; i <= n; i++) if (g[u][i] && !dfs(i, 3 - c)) return false;return true;
}
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}// suf[i]记录a[i]后最小的数int minnum = n;for (int i = n - 1; i >= 1; i--) {suf[i] = minnum;if (a[i] < a[minnum]) minnum = i;}for (int i = 1; i < n; i++)for (int j = i + 1; j < n; j++) {// 寻找是否存在i<j<k而a[k]<a[i]<a[j]if (a[i] < a[j] && a[suf[j]] < a[i]) {g[i][j] = g[j][i] = 1;}}bool ok = true;for (int i = 1; i <= n; i++)if (color[i] == 0) {ok = dfs(i, 1);if (!ok) break;}if (!ok) printf("0\n");else {int cur = 1, i = 1, idx = 0;stack<int> s1, s2;while (cur <= n || i <= n) {if (!s1.empty() && s1.top() == cur) {ans[++idx] = 1;cur++;s1.pop();} else if (!s2.empty() && s2.top() == cur) {// s2出栈是d操作，但此时如果有合适的a操作可做则做a操作if (i <= n && color[i] == 1 && (s1.empty() || s1.top() > a[i])) {ans[++idx] = 0;s1.push(a[i]); i++;} else {ans[++idx] = 3;cur++; s2.pop();}} else if (i <= n && color[i] == 1) {ans[++idx] = 0;s1.push(a[i]); i++;} else if (i <= n && color[i] == 2) {ans[++idx] = 2;s2.push(a[i]); i++;}}for (int i = 1; i <= idx; i++)printf("%c%c", 'a' + ans[i], i == idx ? '\n' : ' ');}return 0;
}