参考资料

题目大意.

给出一个二分图，你要给边染色，使同色边不相邻。求最小色数并构造一组方案。

……其实你不需要使色数最小，设最小色数为 $C$$C$，你只要构造一个色数为 $2^{\lceil {\log }_{2}C\rceil }$$2^{\lceil\log_2C\rceil}$ 的方案即可。

$n_L,n_R\le {10}^5,m\le 5\times {10}^5$$n_L,n_R\le 10^5,m\le 5\times10^5$。

时限 6s。

首先，显然地 $C$$C$ 肯定有上界 $max\text{deg}$$\max \text{deg}$。然后……做了这么多图论题你还不清楚套路吗？没错，它同时也是下界。

证明. (为什么 $max\text{deg}$$\max\text{deg}$ 就是最小色数)

可见，如果我们能找出一组互不相邻的边集 $S$$S$，使得 $G/S$$G/S$ 中每个点的度数都 $\le max\text{deg}-1$$\le \max\text{deg}-1$ 就可以根据归纳法证完了。

考虑左部点（下记为 $V_L$$V_L$）中达到 $max\text{deg}$$\max\text{deg}$ 的点集 $V_L^m$$V^m_L$。$V_L^m$$V_L^m$ 到右部点 $V_R$$V_R$ 必有一完美匹配（根据 Hall 定理，如果此结论不成立，右部必存在一个度数 $>max\text{deg}$$>\max\text{deg}$ 的点，这是不可能的）。对右部点有类似结论。

现在考虑这两个匹配的并 $S^{\prime }$$S'$。显然 $S^{\prime }$$S'$ 中可能有相邻边，相邻边构成的连通块要么是路径要么是偶环。

• 如果是奇路径，保留较多的一半边；
• 如果是偶路径 / 偶环，任意保留一半数量的边。

不难验证，这就构造了一个合法的 $S$$S$。

当然，每次求两遍匹配必然是不可接受的，所以要注意利用 $2^{\lceil {\log }_{2}C\rceil }$$2^{\lceil\log_2C\rceil}$ 的性质。知道 $C=max\text{deg}$$C=\max\text{deg}$ 后，大致思路就很明显了：每次试图把边集分为两半，并让每一半中的最大度数 $\le \lceil C/2\rceil$$\le \lceil C/2\rceil$。

具体来说，一旦发现有两条边相邻于点 $u$$u$ 就强制让它们的颜色相反，并认为 $u$$u$ 不具有这两条邻边（所以每个点总是最多只有一条邻边，也就最多余下一个未"消掉"的度数）。并查集维护一下就好。顺便，由于环总是偶环，不需要担心非树边。

xxxxxxxxxx
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int maxn = 500005;
int nL, nR, m;
int clr[maxn], idx;
struct edge { int u, v, id; };

int fa[maxn], val[maxn];
pii find(int x) {
    if(fa[x] == x) return make_pair(x, 0);
    pii tmp = find(fa[x]);
    return make_pair(fa[x] = tmp.first, val[x] ^= tmp.second);
}
void merge(int x, int y) {
    pii fx = find(x), fy = find(y);
    if (fx.first == fy.first) return;
    fa[fx.first] = fy.first;
    val[fx.first] = (fx.second == fy.second);
}
int D[maxn];
void solve(const vector<edge> &E) {
    for (edge e : E) D[e.u] = D[e.v] = -1;
    for (edge e : E) fa[e.id] = e.id, val[e.id] = 0;
    bool flg = 0;
    for (edge e : E) {
        int u = e.u, v = e.v;
        if (D[u] < 0) D[u] = e.id;
        else flg = 1, merge(D[u], e.id), D[u] = -1;
        if (D[v] < 0) D[v] = e.id;
        else flg = 1, merge(D[v], e.id), D[v] = -1;
    }
    if (!flg) {
        idx++;
        for (edge e : E) clr[e.id] = idx;
        return;
    }
    vector<edge> E0, E1;
    for (edge e : E)
        if (find(e.id).second) E1.push_back(e);
        else E0.push_back(e);
    solve(E0); solve(E1);
}

int main() {
    memset(clr, -1, sizeof(clr));
    scanf("%d%d%d", &nL, &nR, &m);
    vector<edge> E(m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &E[i].u, &E[i].v);
        E[i].id = i;
        E[i].v += nL;
    }
    solve(E);
    printf("%d\n", idx);
    for (int i = 0; i < m; i++)
        printf("%d\n", clr[i]);
}