Color

题意：
给与一个二分图，给边染色，连接同一端点的边的颜色不能相同，求最少用多少种颜色才能完成染色？

思路：
二分图最大匹配的匈牙利算法，对一条边进行染色，设一个端点最小可染的颜色为x，另一个端点最小可染的颜色为x.
①x==y,该边染成x.
②x<y,将该边强行染成x，最小可染颜色为y的点显然已经有了一条为x的边，所以将原先为x的边强行染为y，然后原先为x的边指向的点只好将原先为y的边再强行染成x（如果该点y颜色没有用，则该为边改为y，x颜色标识没用，条件可行），不断进行下去，直到可行为止。

代码：

#include <bits/stdc++.h>
#define inf 99824435300000
using namespace std;

typedef long long ll;

map<int,int> ma;
int bian[1005][2005];
int color[2005];

void dfs(int u, int v,int x,int y)
{
    int xia=bian[v][x];
    bian[u][x]=v;
    bian[v][x]=u;
    if(xia==0)
    {
        bian[v][y]=0;
    }
    else
    {
        dfs(v,xia,y,x);
    }
}

int main()
{
    int n, m, zui=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u, v, x=1, y=1;
        scanf("%d%d",&u,&v);
        ma[u*10000+v]=i;
        ma[v*10000+u]=i;
        while(bian[u][x])
        {
            x++;
        }
        while(bian[v][y])
        {
            y++;
        }
        if(x>y)
        {
            swap(u,v);
            swap(x,y);
        }
        zui=max(zui,y);
        if(x==y)
        {
            bian[u][x]=v;
            bian[v][y]=u;
        }
        else
        {
            dfs(u,v,x,y);
        }
    }
    printf("%d\n",zui);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=zui;j++)
        {
            if(bian[i][j])
            {
                int k=i*10000+bian[i][j];
                color[ma[k]]=j;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",color[i]);
    }
    return 0;
}