构建二分图，新建超级源汇点，所有边权为1，跑一次dinic，最大流即可最大匹配，关键是方案输出，遍历所有边（除去关于s,t的边），满流的边即可一组匹配。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m;int nume;int e[10000][3];int head[105];
const int inf=0x3f3f3f3f;
int vis[105];int level[105];
bool bfs()
{
for(int i=0;i<=n+1;i++)
vis[i]=level[i]=0;
queue<int>q;q.push(0);vis[0]=1;
while(!q.empty())
{
int cur=q.front();q.pop();
for(int i=head[cur];i!=-1;i=e[i][1])
{ int v=e[i][0];
if(!vis[v]&&e[i][2]>0)
{
level[v]=level[cur]+1;
if(v==n+1)return 1;
vis[v]=1;
q.push(v);
}
}
}
return vis[n+1];
}
int dfs(int u,int minf)
{
if(minf==0||u==n+1)return minf;
int sumf=0,f;
for(int i=head[u];i!=-1&&minf;i=e[i][1])
{
int v=e[i][0];
if(level[v]==level[u]+1&&e[i][2]>0)
{
f=dfs(v,minf<e[i][2]?minf:e[i][2]);
e[i][2]-=f;e[i^1][2]+=f;
minf-=f;sumf+=f;
}
}
return sumf;
}
void addedge (int f,int to,int w)
{
e[nume][0]=to;e[nume][1]=head[f];head[f]=nume;
e[nume++][2]=w;
e[nume][0]=f;e[nume][1]=head[to];head[to]=nume;
e[nume++][2]=0;
}
int dinic()
{
int sum=0;
while(bfs())
sum+=dfs(0,inf);
return sum;
}
int main()
{
scanf("%d%d",&m,&n);
nume=0; int i,j;
for(int i=0;i<=n+1;i++)
head[i]=-1;
for(int i=1;i<=m;i++)
addedge(0,i,1);
scanf("%d%d",&i,&j);
while(i!=-1&&j!=1)
{
addedge(i,j,1);
scanf("%d%d",&i,&j);
}
for(int i=m+1;i<=n;i++)
addedge(i,n+1,1);
int ans=dinic();
if(ans==0){printf("No Solution!
");return 0;}
printf("%d
",ans);
for(int i=1;i<=m;i++) //开始还跑bfs，看了群主的代码才发现自己的愚蠢，直接遍历边即可。
for(int j=head[i];j!=-1;j=e[j][1])
{ if(e[j][2]==0&&e[j][0]!=0&&j%2==0) //取前进的边即可
printf("%d %d
",i,e[j][0]);
}
return 0;
}