Educational Codeforces Round 2 Edge coloring of bipartite graph

题意：

输入一个二分图，用最少的颜色数给它的每条边染色，使得同一个顶点连的边中颜色互不相同。

输出至少需要的颜色数和任意一种染色方案。

分析：

证明不会，只说一下(偷瞄巨巨代码学到的)做法。

假设点的最大度数为\(M\)，那么至少需要\(M\)种颜色。

下面给出一种构造方法：

对于一条边\((u, \, v)\)，分别找出对于\(u\)和\(v\)还没用到的颜色\(c_1\)和\(c_2\)。

• 如果\(c_1=c_2\)，直接用颜色\(c_1\)给这条边染色就行了。
• 如果\(c_1 \neq c_2\)，和匈牙利算法的思想一样，我们先给边\((u, \, v)\)染上颜色\(c_1\)。
  
  对于之前和\(v\)染上颜色\(c_1\)的点t，我们用颜色\(c_2\)给边\((v, \, t)\)染色。
  
  如果还有颜色\(c_2\)和\(t\)冲突，持续这个过程，继续把新的颜色腾出来。

这种做法还能顺便解决掉UVa 10615

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1000 + 10;

const int maxm = 100000 + 10;

int col[2][maxn][maxn];

int id[maxn][maxn];

int ans[maxm];

void dfs(int p, int u, int v, int c1, int c2) {

	int t = col[p^1][v][c1];

	col[p][u][c1] = v; col[p^1][v][c1] = u;

	if(!t) {

		col[p^1][v][c2] = 0;

		return ;

	}

	dfs(p^1, v, t, c2, c1);

}

int main()

{

	int n, m, k;

	scanf("%d%d%d", &n, &m, &k);

	int cnt = 0;

	for(int i = 1; i <= k; i++) {

		int u, v; scanf("%d%d", &u, &v);

		id[u][v] = i;

		int c1 = 1, c2 = 1;

		while(col[0][u][c1]) c1++;

		while(col[1][v][c2]) c2++;

		cnt = max(cnt, max(c1, c2));

		if(c1 == c2) {

			col[0][u][c1] = v;

			col[1][v][c1] = u;

		} else {

			dfs(0, u, v, c1, c2);

		}

	}

	printf("%d\n", cnt);

	for(int i = 1; i <= n; i++)

		for(int j = 1; j <= cnt; j++)

			if(col[0][i][j])

				ans[id[i][col[0][i][j]]] = j;

	for(int i = 1; i <= k; i++) printf("%d ", ans[i]);

	printf("\n");

	return 0;

}