《飞行员配对方案问题》 C++代码 ← 链式前向星

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

const int N=1e4+5;
bool st[N];
int match[N];
int h[N],ne[N<<1],e[N<<1],idx;
int n,m;

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int find(int u) {
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!st[j]) {
            st[j]=true;
            /*If girl j doesn't have a boyfriend,
            or her previous boyfriend can book other girls he likes.
            Pairing successful. */
            if(!match[j] || find(match[j])) {
                match[j]=u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    memset(h,-1,sizeof h);
    cin>>m>>n;
    while(1) {
        int x,y;
        cin>>x>>y;
        if(x==-1 && y==-1) break;
        add(x,y);
    }

    int ans=0;
    for(int i=1; i<=m; i++) {
        memset(st,false,sizeof st);
        if(find(i)) ans++;
    }
    cout<<ans<<endl;

    for(int i=m+1; i<=n; i++) {
        if(match[i]) {
            cout<<match[i]<<" "<<i<<endl;
        }
    }

    return 0;
}

/*
in:
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

out:
4
1 7
2 9
3 8
5 10
*/