跳转至

CF600F

知识点

  • 二分图
  • 染色

题意简述

给定一个点集大小分别为 \(a, b\),有 \(m\) 条边的二分图,

问将其染成 任意两相邻边颜色均不同 最少需要多少种颜色,并输出任意一种方案1

数据范围:\(1 \le a, b \le 10^3\)\(1 \le m \le 10^5\)

解题思路

边染色一个二分图,最少需要的颜色种数为图中顶点的最大度数。

具体证明可以看 Story about edge coloring of graph

然后我们可以钦定一个点出边的颜色,如果有不符合的就顺着链摸下去修改颜色即可。

时间复杂度为 \(O(m(a + b))\)

代码实现

核心部分已用高亮标出。

Code
 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
#include <bits/stdc++.h>
#define LL long long

const int N = 2e3 + 5;
const int M = 2e5 + 5;

int a, b, m, ans;
int u[M], v[M], deg[N], col[N][N];

int32_t main() {
    scanf("%d %d %d", &a, &b, &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d", &u[i], &v[i]);
        v[i] += a;
        ++deg[u[i]], ++deg[v[i]];
    }
    for(int i = 1; i <= a + b; ++i)
        ans = std::max(ans, deg[i]);
    for(int i = 1; i <= m; ++i) {
        int c1, c2;
        for(c1 = 1; c1 <= ans; ++c1) if(!col[u[i]][c1]) break;
        for(c2 = 1; c2 <= ans; ++c2) if(!col[v[i]][c2]) break;
        col[u[i]][c1] = v[i];
        col[v[i]][c2] = u[i];
        if(c1 == c2) continue;
        for(int c0 = c2, x = v[i]; x; x = col[x][c0], c0 ^= c1 ^ c2)
            std::swap(col[x][c1], col[x][c2]);
    }
    printf("%d\n", ans);
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= ans; ++j)
            if(col[u[i]][j] == v[i]) {
                printf("%d ", j);
                break;
            }
    return 0;
}