问题描述
给出一个一般图，现在将它的每条边染色，使得任意两条相邻（有公共顶点）的边颜色不同。请给出一种染色方案，使得用到的颜色数量不超过Δ(G)+1。
解决方案
试想，现在我们碰到了一条新的边(u, v)，它还没被染色。我们想把它染成一个v没有见过的颜色A。不幸的是：u见过这个颜色了——(u, v_0)被染成颜色A了。。。 u对v说：要不我们俩先染成颜色A吧，我让v_0换个颜色染。v说：好呀！ 那现在(u, v_0)想被染成v_0没有见过的颜色B。不幸的是：u见过颜色B了——(u, v_1)是颜色B。u如法炮制，先跟v_0染着颜色B，再跟v_1另请高明。 如此转转不已，总能找到一个v_l，要么新的颜色u和v_l都没见过，要么它见过某颜色，但是邻居在之前的人们里，这样这个过程不得不停下来了。 如果是前者，那非常好：每对顶点的颜色挪一下，最终让(u, v_l)涂上新的没见过的颜色就行啦！ 如果是后者：我们还有一个办法：找到在之前人们里的那个邻居，让他和u连接的颜色d先变成全新的没见过的颜色c，再找到一个能接受颜色d的顶点v_w，在前面仍然挪一下，最后给(u, v_w)涂上颜色d。 于是，我们的思路就有了！
困难之处
我们称一个可以挪动的序列为一个扇，我们想要找到极大的扇来挪动。但是，找极大扇的过程在朴素想法下是O(n^2)的！于是我们需要精巧的数据结构构造： 考虑用数组存储每个顶点没见过的颜色，每次取数组头的颜色作为下一个人尝试的新颜色。毕竟我们不需要考虑颜色的顺序，这个取颜色的过程可以是O(1)的。 我们还可以记录每个点由某个颜色连接到的顶点，这样无论是考察一个点是否用过某个颜色还是寻找新顶点都可以在O(1)的时间下完成！ 遍历边涂色，每个边最坏要把所有点加进扇，所以最终复杂度是O(mn)的。
代码示例
这是我写的垃圾代码，仅供参考。。。
#include <algorithm>
#include <cstdio>
#include <unordered_map>
#include <vector>
#include <numeric>
using std::hash;
using std::iota;
using std::make_pair;
using std::max;
using std::pair;
using std::swap;
using std::unordered_map;
using std::vector;
struct PairHash
{
size_t operator()(const pair<int, int> &p) const noexcept
{
return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
}
};
void popHead(vector<int> &vec)
{
if (vec.empty())
{
return;
}
vec[0] = vec.back();
vec.pop_back();
return;
}
void removeValue(vector<int> &vec, int x)
{
for (int i = 0; i < vec.size(); ++i)
{
if (vec[i] == x)
{
vec[i] = vec.back();
vec.pop_back();
return;
}
}
return;
}
void modifyValue(vector<int> &vec, int x, int y)
{
for (int i = 0; i < vec.size(); ++i)
{
if (vec[i] == x)
{
vec[i] = y;
return;
}
}
return;
}
class Graph
{
public:
int size, maxDegree;
struct Edge
{
int from, to;
};
vector<Edge> E;
vector<int> degree;
unordered_map<pair<int, int>, int, PairHash> G;
vector<vector<int>> adj;
explicit Graph(int x)
{
size = x;
maxDegree = 0;
degree.resize(x, 0);
adj.resize(x);
}
void addEdge(int u, int v)
{
G[{u, v}] = E.size();
adj[u].push_back(E.size());
adj[v].push_back(E.size());
E.push_back({u, v});
++degree[u];
++degree[v];
maxDegree = max({maxDegree, degree[u], degree[v]});
return;
}
vector<int> edgeColoring()
{
vector<vector<int>> edgeColor(size, vector<int>(maxDegree + 1, -1));
vector<int> color(E.size(), -1);
vector<vector<int>> freeColor(size, vector<int>(maxDegree + 1));
for (int i = 0; i < size; ++i)
{
iota(freeColor[i].begin(), freeColor[i].end(), 0);
}
auto getEdge = [&](int u, int v)
{
if (G.count({u, v}))
{
return G[{u, v}];
}
else
{
return G[{v, u}];
}
};
auto findFan = [&](int u, int v)
{
vector<int> fan;
vector<int> used(size, 0);
fan.push_back(v);
used[v] = 1;
int c, w;
while (1)
{
c = freeColor[fan.back()][0];
if (edgeColor[u][c] == -1)
{
break;
}
w = edgeColor[u][c];
if (used[w])
{
break;
}
fan.push_back(w);
used[w] = 1;
}
return fan;
};
auto rotateFan = [&](const vector<int> &fan, int u)
{
if (fan.size() <= 1)
{
return;
}
for (int i = 0; i < fan.size() - 1; ++i)
{
popHead(freeColor[fan[i]]);
if (color[getEdge(u, fan[i])] != -1)
{
freeColor[fan[i]].push_back(color[getEdge(u, fan[i])]);
edgeColor[fan[i]][color[getEdge(u, fan[i])]] = -1;
}
color[getEdge(u, fan[i])] = color[getEdge(u, fan[i + 1])];
edgeColor[u][color[getEdge(u, fan[i])]] = fan[i];
edgeColor[fan[i]][color[getEdge(u, fan[i])]] = u;
}
int fanLast = fan[fan.size() - 1];
freeColor[fanLast].push_back(color[getEdge(u, fanLast)]);
edgeColor[fanLast][color[getEdge(u, fanLast)]] = -1;
color[getEdge(u, fanLast)] = -1;
return;
};
auto flipPath = [&](int u, int c, int d)
{
modifyValue(freeColor[u], c, d);
while (1)
{
swap(edgeColor[u][c], edgeColor[u][d]);
if (edgeColor[u][c] == -1)
{
break;
}
color[getEdge(u, edgeColor[u][c])] = c;
u = edgeColor[u][c];
swap(c, d);
}
modifyValue(freeColor[u], d, c);
return;
};
for (auto e : E)
{
int u = e.from, v = e.to;
vector<int> fan = findFan(u, v);
int d = freeColor[fan[fan.size() - 1]][0];
if (edgeColor[u][d] == -1)
{
rotateFan(fan, u);
color[getEdge(u, fan[fan.size() - 1])] = d;
popHead(freeColor[fan[fan.size() - 1]]);
edgeColor[u][d] = fan[fan.size() - 1];
edgeColor[fan[fan.size() - 1]][d] = u;
removeValue(freeColor[u], d);
}
else
{
int c = freeColor[u][0], w = 0;
flipPath(u, c, d);
for (int i = 0; i < fan.size(); ++i)
{
if (edgeColor[fan[i]][d] == -1)
{
w = i;
break;
}
}
vector<int> subFan(fan.begin(), fan.begin() + w + 1);
rotateFan(subFan, u);
color[getEdge(u, fan[w])] = d;
removeValue(freeColor[fan[w]], d);
removeValue(freeColor[u], d);
edgeColor[u][d] = fan[w];
edgeColor[fan[w]][d] = u;
}
}
return color;
}
};
void read(int &x)
{
x = 0;
char ch = getchar();
while (ch < 48 || ch > 57)
{
ch = getchar();
}
while (ch >= 48 && ch <= 57)
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return;
}
int main()
{
int T, n, m, u, v;
read(T);
for (int t = 0; t < T; ++t)
{
read(n);
read(m);
Graph g(n);
for (int j = 0; j < m; ++j)
{
read(u);
read(v);
g.addEdge(u - 1, v - 1);
}
vector<int> ans = g.edgeColoring();
for (int j = 0; j < m; ++j)
{
printf("%d ", ans[j] + 1);
}
printf("\n");
}
return 0;
}
实际测试
由于常数过大，上述示例代码有时跑得比O(mn^2)的算法还慢。。。