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] << " ";

}