NC14254 Color(二分图最大匹配)

题目链接

题意：



题解：

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9+7;
//const int mod = 998244353;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6+10;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
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);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    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;
}