SAM I AM - UVa 11419 AC

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

const int MAXV = 2010;
const int MAXE = (2010*2010+2010);
const int inf = 0x3f3f3f3f;

int nV, vE;
int n;
int r,c;
int s,t;

int lastEdge[MAXV];

struct edge {
    int dst,f,c;
    int prev;
};

edge ls[MAXE];
int currEdge[MAXV];
queue<int> q;
int d[MAXV];

void makeEdge(int src, int dst, int cap) {
    ls[vE].dst=dst, ls[vE].c=cap, ls[vE].f=0;
    ls[vE].prev=lastEdge[src];
    lastEdge[src]=vE++;
}

bool bfs() {
    while (!q.empty()) q.pop();
    memset(d,0x3f,sizeof(d));

    d[s]=0;
    q.push(s);

    for (int i=0; i<nV; i++)
        currEdge[i]=lastEdge[i];

    while (!q.empty()) {
        int u=q.front();
        if (u==t)
            return true;
        q.pop();

        for (int i=lastEdge[u]; i!=-1; i=ls[i].prev) {
            int v=ls[i].dst;

            if (ls[i].c-ls[i].f==0) continue;
            if (d[v]!=inf) continue;

            d[v]=d[u]+1;
            q.push(v);
        }
    }

    return false;
}

int dfs(int u, int flow) {
    if (u==t) return flow;

    for (int& i=currEdge[u]; i!=-1; i=ls[i].prev) {
        int v=ls[i].dst;

        if (d[v]!=d[u]+1) continue;
        if (ls[i].c-ls[i].f==0) continue;

        int tmpF = dfs(v,min(ls[i].c-ls[i].f, flow));

        if (tmpF) {
            ls[i].f+=tmpF;
            ls[i^1].f-=tmpF;
            return tmpF;
        }
    }

    return 0;
}

int dinic() {
    int maxFlow=0;

    while (bfs())
        while (int flow=dfs(s,inf))
            maxFlow+=flow;

    return maxFlow;
}

bool tmark[MAXV];

void recDfs(int u) {
    tmark[u]=true;

    for (int i=lastEdge[u]; i!=-1; i=ls[i].prev) {
        if (tmark[ls[i].dst])
            continue;
        if (ls[i].dst>=r+c)
            continue;

        if (u<r) {
            if (ls[i].c-ls[i].f>0)
                recDfs(ls[i].dst);
        }
        else
            if (ls[i^1].c-ls[i^1].f==0)
                recDfs(ls[i].dst);
    }
}

bool mark[MAXV];

void recover() {
    memset(tmark,0,sizeof(tmark));
    memset(mark,0,sizeof(mark));

    for (int i=lastEdge[s]; i!=-1; i=ls[i].prev)
        if (ls[i].c-ls[i].f>0)
            recDfs(ls[i].dst);

    for (int i=0; i<r; i++)
        if (!tmark[i]) mark[i]=true;
    for (int i=0; i<c; i++)
        if (tmark[i+r]) mark[i+r]=true;
}

int main() {
    while (1) {
        scanf("%d %d %d", &r,&c,&n);
        if (!r && !c && !n) break;

        memset(lastEdge,-1,sizeof(lastEdge));

        nV=r+c+2, vE=0;
        s=r+c, t=r+c+1;

        for (int k=0; k<n; k++) {
            int x,y;
            scanf("%d %d", &x,&y);
            x--, y--;

            makeEdge(x,y+r,1);
            makeEdge(y+r,x,0);
        }

        for (int i=0; i<r; i++) {
            makeEdge(s,i,1);
            makeEdge(i,s,0);
        }

        for (int i=0; i<c; i++) {
            makeEdge(i+r,t,1);
            makeEdge(t,i+r,0);
        }

        printf("%d", dinic());
        recover();

        for (int i=0; i<r; i++)
            if (mark[i]) printf(" r%d", i+1);
        for (int i=0; i<c; i++)
            if (mark[i+r]) printf(" c%d", i+1);
        printf("\n");
    }
    return 0;
}