每日一题 7月9日 Color 匈牙利算法+同点不同色的二分图的染色

题目链接：https://ac.nowcoder.com/acm/problem/14254
题目大意：

思路：参考大佬的思路：

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

map<int, int> mp[1005];
int cloer[1005][1005];
int vis[2005];
void dfs(int x, int y, int c1, int c2){
    int to=cloer[y][c1];
    cloer[x][c1]=y, cloer[y][c1]=x;//强行把x-y染成c1。让y把c1的正确那条边染成c2
    if(!to){
        cloer[y][c2]=0;
    }
    else{
        dfs(y, to, c2, c1);
    }

}

int main(){
    int n, m, x, y; scanf("%d%d", &n, &m);
    int ans=0;
    for(int i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        mp[x][y]=mp[y][x]=i;
        int c1=1, c2=1;
        while(cloer[x][c1]){
            c1++;
        }
        while(cloer[y][c2]){
            c2++;
        }
        if(c1>c2){
            swap(x, y); swap(c1, c2);
        }
        ans=max(ans, c2);
        if(c1==c2){//如果最小没有使用的颜色一样，就直接染色
            cloer[x][c1]=y;
            cloer[y][c1]=x;
        }
        else{
            dfs(x, y, c1, c2);//否则找增广路
        }
    }
    printf("%d\n", ans);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=ans; j++){
            int to=cloer[i][j];
            if(to){
                vis[mp[i][to]]=j;
            }
        }
    }
    for(int i=1; i<=m; i++){
        printf("%d\n", vis[i]);
    }

    return 0;
}