algorithm - 最大二分匹配

Question

目前最著名的最大二分匹配算法是 O(√VE)。

下面是我解决上述问题的算法:给定两个集合 S1 和 S2 以及它们之间的 E 边。

step1:将S1和S2按度数升序排列

第2步:按排序顺序挑选集合中的元素并将其分配给另一个集合中的下一个空闲元素，计算匹配的数量。

第3步:在S1上执行第2步，然后在S2上执行。

第 4 步:取第 3 步的最大值。

这使得上述算法的复杂度为 O(Vlog(V)+(V+E))。

我无法证明上述算法的正确性，所以任何人都可以帮助我解决上述示例失败的任何反例，因为该算法不适用于 spoj 问题 MATCHING所以算法是错误的，但无法找出反例。

谢谢

#include<bits/stdc++.h>
#define ll long long int
using namespace std;


int main(){

    ll c,b,p;
    cin >> c >> b >> p;
    c+=1;
    b+=1;
    ll mx = max(c,b);
    c =mx;
    b =mx;
    vector<ll> adjcow[c];
    vector<ll> adjbull[b];

    for(ll i=0; i<p; i++){
        ll x,y;
        cin >> x >> y;
        adjcow[x].push_back(y);
        adjbull[y].push_back(x);
    }

    /*
    for(ll i=0; i<c; i++){
        cout << i << " ";
        for(auto x:adjcow[i])
            cout << x << " ";
        cout << "\n";
    }

    for(ll i=0; i<b; i++){
        cout << i << " ";
        for(auto x : adjbull[i])
            cout << x << " ";
        cout << endl; 
    }
    */

    vector<pair<ll, ll>> deg1(c);
    vector<pair<ll, ll>> deg2(b);


    for(ll i=0; i<c; i++){
        ll count = 0;
        for(auto x: adjcow[i])
            count++;
        deg1[i] = {count, i};
    }

    for(ll i=0; i<b; i++){
        ll count = 0;
        for(auto x: adjbull[i])
            count++;
        deg2[i] = {count,i};
    }

    sort(deg1.begin(), deg1.end());
    sort(deg2.begin(), deg2.end());

    vector<bool> isTaken1(c,0);
    vector<bool> isTaken2(b,0);

    /*
    for(ll i=0; i<c; i++)
        cout << deg1[i].first << " " << deg1[i].second  << ", ";

    cout << endl;

    for(ll i=0; i<b; i++) 
        cout << deg2[i].first <<" "<< deg2[i].second  << ", ";

    cout << endl;
    */

    ll ansCow =0;
    for(auto x:deg1){
        ll node = x.second;
        for(auto u: adjcow[node]){
            if(isTaken1[u]==0){
    //          cout << node << "-> " << u << "\n";
                isTaken1[u] = 1;
                ansCow++;
                break;
            }
        }
    }

    //cout << "\n\n";

    ll ansBull =0;
    for(auto x:deg2){
        ll node = x.second;
        for(auto u: adjbull[node]){
            if(isTaken2[u]==0){
    //          cout << node << "->" << u << "\n";
                isTaken2[u] = 1;
                ansBull++;
                break;
            }
        }
    }

    cout << max(ansCow, ansBull) << "\n";
}

输入:

5 4 6
5 2
1 2
4 3
3 1
2 2
4 4

Answer 1

反例如下所示。请注意，每个节点的度数均为 2，因此排序无效。从左往右连接时，如果1选A，2选B，则3不能连接。所以结果是2，从右往左连接的时候，如果A选1，B选2，那么C就不能连接。结果又是2。但正确结果是3，1接C，2接B，3接A。

程序的输入是:

3 3 6
1 1
1 3
2 2
2 3
3 1
3 2