HDU 2819暗黙的二分図マッチング

http://acm.hdu.edu.cn/showproblem.php?pid=2819
この問題は一見マトリックス変換問題と見られますが、マトリックスなどでもできると思います
でも分析してみればわかる
対角線にまとめるにはすべて1で、テーマは行変換と列変換を許可します
しかし観察から分かるように、行変換または列変換のいずれかを完了すればよい
donser[i][j]=1はiを表し、j位置が1であればjからiに変換するだけ(すなわち、i,j行を交換する)
中間プロシージャ用queueの出力
dfs遍歴を加えればよい

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int donser[1002][1002];
bool used[1002];
int leave[1002],a[1002],b[1002];
int M,num,abc,j;
queue<int >que;
void swap(int i,int j)
{
    int t=leave[i];leave[i]=leave[j];leave[j]=t;
}
int dfs(int x)
{
    for(int i=1;i<=M;i++)
    {
        if(donser[x][i]&&!used[i])
        {
            used[i]=true;
            if(!leave[i]||dfs(leave[i]))
            {
                leave[i]=x;
                return 1;
            }
            
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d",&M))
    {
        memset(donser,0,sizeof(donser));
        memset(leave,0,sizeof(leave));
        for(int i=1;i<=M;i++)
        {
            for(j=1;j<=M;j++)
            {
                scanf("%d",&num);
                if(num) {donser[i][j]=1;}
            }
        }
        num=abc=0;
        for(int i=1;i<=M;i++)
        {
            memset(used,0,sizeof(used));
            if(dfs(i)){abc++;}
        }
        if(abc!=M) {cout<<"-1"<<endl;continue;}
        abc=0,j=1;
        for(int i=1;i<=M;i++)
        {
            for(j=1;j<=M && leave[j]!=i ;j++);
            if(i!=j)
            {
                abc++;
                que.push(i);
                que.push(j);
                swap(i,j);
            }
        }
        cout<<abc<<endl;
        while(!que.empty())
        {
            cout<<"C "<<que.front();
            que.pop();
            cout<<" "<<que.front()<<endl;
            que.pop();
        }
        abc=0;
    }
    return 0;
}