Uva-11419-SAM I AM

この問題は二分図でマッチングして、白書の上の問題です.最も偶然なのは最後に再び未整合点をマッチングすることで、具体的な爆弾の位置を算出することができると思います.最初は他の方法でずっとwaを試して、それから他の人のコードを見て長い間考えてやっと分かった.
コード:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=2e3;
const int maxm=3e6;
int e,r,c,n,head[maxn],pnt[maxm],nxt[maxm],linkl[maxn],linkr[maxn];
bool S[maxn],T[maxn];
void AddEdge(int u,int v)
{
    pnt[e]=v;nxt[e]=head[u];head[u]=e++;
}
bool match(int u)
{
    S[u]=1;
    for(int i=head[u];i!=-1;i=nxt[i])
        if(!T[pnt[i]])
        {
            T[pnt[i]]=1;
            if(!linkl[pnt[i]]||match(linkl[pnt[i]]))
            {
                linkl[pnt[i]]=u;
                linkr[u]=pnt[i];
                return true;
            }
        }
    return false;
}
int main()
{
    while(scanf("%d%d%d",&r,&c,&n)&&(r+c+n))
    {
        e=0;
        memset(head,-1,sizeof(head));
        memset(linkl,0,sizeof(linkl));
        memset(linkr,0,sizeof(linkr));
        for(int i=0;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            AddEdge(u,v);
        }
        int ans=0;
        for(int i=1;i<=r;i++)
        {
            memset(S,0,sizeof(S));
            memset(T,0,sizeof(T));
            if(match(i))
                ans++; 
        }
        memset(S,0,sizeof(S));
        memset(T,0,sizeof(T));
        for(int i=1;i<=r;i++)
        {
            if(!linkr[i])
                match(i);
        }
        printf("%d",ans);
        for(int i=1;i<=r;i++)
            if(!S[i])
                printf(" r%d",i);
        for(int i=1;i<=c;i++)
            if(T[i])
                printf(" c%d",i);
        printf("
");
    }
    return 0;
}