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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| 题解：
n < = 1 e 3 , m < = 2 e 3 n <=1e3,m<=2e3n<=1e3,m<=2e3
题 目 要 求 转 化 一 下 ， 就 是 从 一 个 点 出 入 的 所 有 边 ， 颜 色 必 须 不 同 题目要求转化一下，就是从一个点出入的所有边，颜色必须不同题目要求转化一下，就是从一个点出入的所有边，颜色必须不同
但 是 从 另 一 个 点 出 入 的 边 ， 可 能 与 这 些 颜 色 相 同 ， 可 能 不 同 但是从另一个点出入的边，可能与这些颜色相同，可能不同但是从另一个点出入的边，可能与这些颜色相同，可能不同
使 用 最 少 颜 色 ， 就 是 使 得 这 些 颜 色 尽 量 相 同 的 多 一 些 使用最少颜色，就是使得这些颜色尽量相同的多一些使用最少颜色，就是使得这些颜色尽量相同的多一些
所 以 ， 每 次 找 到 一 条 边 ， 他 的 两 个 端 点 在 这 次 查 找 都 没 出 现 过 所以，每次找到一条边，他的两个端点在这次查找都没出现过所以，每次找到一条边，他的两个端点在这次查找都没出现过
这 样 找 出 的 一 组 边 就 可 以 用 相 同 颜 色 这样找出的一组边就可以用相同颜色这样找出的一组边就可以用相同颜色
并 且 这 是 一 个 二 分 图 ， 所 以 就 成 了 二 分 图 的 最 大 匹 配 问 题 并且这是一个二分图，所以就成了二分图的最大匹配问题并且这是一个二分图，所以就成了二分图的最大匹配问题
多 次 调 用 二 分 图 最 大 匹 配 ， 为 每 次 匹 配 出 来 的 边 赋 上 颜 色 ， 直 到 全 部 匹 配 多次调用二分图最大匹配，为每次匹配出来的边赋上颜色，直到全部匹配多次调用二分图最大匹配，为每次匹配出来的边赋上颜色，直到全部匹配
但 是 光 这 样 肯 定 还 是 无 法 到 达 最 优 的 但是光这样肯定还是无法到达最优的但是光这样肯定还是无法到达最优的
再 想 一 下 ， 其 实 每 个 点 出 入 的 所 有 边 颜 色 一 定 不 同 再想一下，其实每个点出入的所有边颜色一定不同再想一下，其实每个点出入的所有边颜色一定不同
那 么 答 案 就 是 度 数 最 大 的 那 个 点 那么答案就是度数最大的那个点那么答案就是度数最大的那个点
每 次 匹 配 也 要 先 为 度 数 大 的 进 行 匹 配 每次匹配也要先为度数大的进行匹配每次匹配也要先为度数大的进行匹配
否 则 会 导 致 几 根 可 以 用 相 同 颜 色 的 线 用 了 不 同 颜 色 否则会导致几根可以用相同颜色的线用了不同颜色否则会导致几根可以用相同颜色的线用了不同颜色
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
typedef long long ll;
const int maxn = 1e6+10;
int match[maxn];
vector<int> g[maxn];
bool vis[maxn];
bool dfs(int u) {
for (auto v : g[u]) {
if (!vis[v]) {
vis[v] = 1;
if (!match[v] || dfs(match[v])) {
match[v] = u;
match[u] = v;
return 1;
}
}
}
return 0;
}
int d[maxn],u[maxn],v[maxn],id[maxn];
int col[1010][1010];
bool cmp(int x, int y) {
return d[x] > d[y];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, m, ans = 0;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i];
d[u[i]]++, d[v[i]]++;
ans = max(ans, max(d[u[i]], d[v[i]]));
}
for (int i = 1; i <= n; i++) id[i] = i;
for (int i = 1; i <= ans; i++) {
for (int j = 1; j <= m; j++)
if(!col[u[j]][v[j]]){
g[u[j]].pb(v[j]);
g[v[j]].pb(u[j]);
}
for (int j = 1; j <= n; j++)
match[j] = 0;
sort(id + 1, id + 1 + n, cmp);
for (int j = 1, p = id[j]; j <= n; j++, p = id[j])
if (!match[p]){
for(int k = 1; k <= n; k++) vis[k] = 0;
dfs(p);
}
for (int j = 1; j <= n; j++){
if (match[j])
col[j][match[j]] = i, d[j]--;
g[j].clear();
}
}
cout << ans << endl;
for (int i = 1; i <= m; i++)
cout << col[u[i]][v[i]] << endl;
return 0;
}
|
