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;
}