Editorial for Codeforces Educational 2F - Edge coloring of bipartite graph


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Mike4235

Lời giải

Gọi ~d~ là số lượng đỉnh kề tối đa của các đỉnh trong đồ thị. Ta sẽ chứng minh số màu tối thiểu để tô đồ thị là ~d~ bằng cách sử dụng thuật toán xây dựng đáp án sau.

Ta sẽ tô màu các cạnh trong đồ thị lần lượt theo thứ tự nào đó. Gọi đỉnh ~u~ là tự do với màu ~c~ nếu như tại thời điểm đó không có cạnh nào kề với ~u~ mà được tô bằng màu ~c~.
Gọi cạnh đang xét là cạnh ~(x, y)~

  • Giả dụ tồn tại một màu ~c~ sao cả hai đỉnh tự do với màu ~c~ thì ta đơn giản tô cạnh đó với màu ~c~.
  • Nếu không tồn tại màu ~c~, nhận thấy rằng luôn tồn tại hai màu ~c_1~ sao cho đỉnh ~x~ không tự do với màu ~c_1~ và đỉnh ~y~ tự do với màu ~c_1~, và màu ~c_2~ sao cho đỉnh ~x~ tự do với màu ~c_2~ và đỉnh ~y~ không tự do với màu ~c_2~. Ta sẽ làm cho đỉnh ~y~ tự do với màu ~c_2~.
    Gọi đỉnh ~z~ là đỉnh mà cạnh ~(y, z)~ được tô bằng màu ~c_2~. Nếu đỉnh ~z~ tự do với màu ~c_1~ thì ta sẽ tô lại màu cạnh ~(y, z)~ thành màu ~c_1~ và tô cạnh ~(x, y)~ màu ~c_2~. Nếu không, gọi đỉnh ~w~ là đỉnh mà cạnh ~(z, w)~ được tô bằng màu ~c_1~. Nếu ~w~ tự do với màu ~c_2~ thì ta sẽ tô tương tự. Cứ như vậy luân phiên cho đến khi thỏa mãn. Đảm bảo luôn tô được như vậy vì đồ thị là đồ thị hai phía.

Độ phức tạp: ~\mathcal{O}(n \times m)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5, M = 1e5 + 5;

int a, b, m, d;
int u[M], v[M], res[M];
int deg[2 * N], flag[2 * N][N], id[2 * N][N];

void dfs(int u, int v, int i, int col1, int col2, bool par, bool cont) {
    if (cont) {
        if (par == 0) {
            int x = flag[v][col2];
            int i = id[v][col2];
            flag[v][col2] = 0; id[v][col2] = 0;
            flag[x][col2] = 0; id[x][col2] = 0;
            dfs(v, x, i, col1, col2, par ^ 1, flag[x][col1]);
        }
        else {
            int x = flag[v][col1];
            int i = id[v][col1];
            flag[v][col1] = 0; id[v][col1] = 0;
            flag[x][col1] = 0; id[x][col1] = 0;
            dfs(v, x, i, col1, col2, par ^ 1, flag[x][col2]);
        }
    }

    if (par == 0) {
        flag[u][col2] = v;
        id[u][col2] = i;
        flag[v][col2] = u;
        id[v][col2] = i;
        res[i] = col2;
    }
    else {
        flag[u][col1] = v;
        id[u][col1] = i;
        flag[v][col1] = u;
        id[v][col1] = i;
        res[i] = col1;
    }
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> a >> b >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        v[i] += a;
        deg[u[i]]++; deg[v[i]]++;
        d = max({d, deg[u[i]], deg[v[i]]});
    }

    for (int i = 1; i <= m; i++) {
        int col1 = 0, col2 = 0;
        for (int j = 1; j <= d; j++) if (!flag[u[i]][j] && !flag[v[i]][j]) {
            res[i] = j;
            flag[u[i]][j] = v[i];
            id[u[i]][j] = i;
            flag[v[i]][j] = u[i];
            id[v[i]][j] = i;
            goto nxt;
        }

        for (int j = 1; j <= d; j++) {
            if (flag[u[i]][j] && !flag[v[i]][j]) col1 = j;
            if (!flag[u[i]][j] && flag[v[i]][j]) col2 = j;
        }

        dfs(u[i], v[i], i, col1, col2, 0, 1);
        nxt:;
    }

    cout << d << "\n";
    for (int i = 1; i <= m; i++) cout << res[i] << " ";

}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.