MATCH1 - Cặp ghép không trọng số

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAX   111
using namespace std;
vector<int> gx[MAX];
int matx[MAX];
int maty[MAX];
int tx[MAX];
int ty[MAX];
int m,n;
queue<int> q;
void loadgraph(void) {
    int i,u,v;
    scanf("%d",&m);
    scanf("%d",&n);
    while (scanf("%d%d",&u,&v)==2) {
        gx[u].push_back(v);
     //   gy[v].push_back(u);
    }
}
int findway(const int &s) {
    memset(tx,0,sizeof tx);
    memset(ty,0,sizeof ty);
    while (!q.empty()) q.pop();
    q.push(s);
    int i,p,v;
    while (!q.empty()) {
        p=q.front();q.pop();
        for (i=0;i<gx[p].size();i=i+1) {
            v=gx[p][i];
            if (ty[v]==0 && matx[p]!=v) {
                ty[v]=p;
                if (maty[v]==0) return (v);
                else {
                    tx[maty[v]]=v;
                    q.push(maty[v]);
                }
            }
        }
    }
    return (0);
}
void enlarge(const int &f) {
    int u,v;
    u=ty[f];
    while (u!=0) {
        v=tx[u];
        matx[u]=0;
        maty[v]=0;
        u=ty[v];
    }
    v=f;
    u=ty[f];
    while (u!=0) {
        matx[u]=v;
        maty[v]=u;
        v=tx[u];
        u=ty[v];
    }
}
void maxmatching(void) {
    memset(matx,0,sizeof matx);
    memset(maty,0,sizeof maty);
    int i,t;
    bool cont;
    for (i=1;i<=m;i=i+1) {
        t=findway(i);
        if (t>0) enlarge(t);
    }
}
void print(void) {
    int i,c=0;
    for (i=1;i<=m;i=i+1) c=c+(matx[i]!=0);
    printf("%d\n",c);
    for (i=1;i<=m;i=i+1)
        if (matx[i]>0) printf("%d %d\n",i,matx[i]);
}
int main(void) {
    //freopen("tmp.txt","r",stdin);
    loadgraph();
    maxmatching();
    print();
    return 0;
}

Download