[UVA 11419: SAM I AM](https://uva.onlinejudge.org/external/114/11419.html)

11419.cpp

#include <iostream>
#include <vector>
#include <stack>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::stack;

struct node {
    vector<int> connected;
    bool match;
    int to;
};

/* to avoid specialized version of vector<bool>,
 * use vector<char> instead
 */
bool dfs(int xi, vector<node>& x, vector<node>& y, vector<char>& visited_y) {
    for (auto e : x[xi].connected) {
        if (!visited_y[e]) {
            visited_y[e] = true;

            if (!y[e].match || dfs(y[e].to, x, y, visited_y)) {
                x[xi].match = true;
                y[e].match = true;
                x[xi].to = e;
                y[e].to = xi;
                return true;
            }
        }
    }

    return false;
}

int matching(vector<node>& x, vector<node>& y)
{
    int ans = 0;

    for (unsigned int i = 0; i < x.size(); ++i) {
        vector<char> visited_y(y.size(), 0);

        if (dfs(i, x, y, visited_y))
            ++ans;
    }

    return ans;
}

void tag(
    vector<node>& x,
    vector<node>& y,
    vector<char>& tag_x,
    vector<char>& tag_y
) {
    stack<int> untagged;

    for (unsigned int i = 0; i < x.size(); ++i) {
        if (!x[i].match)
            untagged.push(i);
    }

    while (!untagged.empty()) {
        int xi = untagged.top();
        untagged.pop();
        tag_x[xi] = true;

        for (auto e : x[xi].connected) {
            if (!tag_y[e] && (!x[xi].match || x[xi].to != e)) {
                tag_y[e] = true;
                if (!tag_x[y[e].to])
                    untagged.push(y[e].to);
            }
        }
    }
}

int main()
{
    while (true) {
        int row, col, n;
        cin >> row >> col >> n;
        if (row == 0)
            break;

        vector<node> x(row);
        vector<node> y(col);

        while (n--) {
            int r, c;
            cin >> r >> c;
            --r;
            --c;

            x[r].connected.push_back(c);
            y[c].connected.push_back(r);
        }

        cout << matching(x, y);

        vector<char> tag_x(row, 0);
        vector<char> tag_y(col, 0);

        tag(x, y, tag_x, tag_y);

        for (unsigned int i = 0; i < tag_x.size(); ++i) {
            if (!tag_x[i] && x[i].connected.size() > 0)
                cout << " r" << i + 1;
        }

        for (unsigned int i = 0; i < tag_y.size(); ++i) {
            if (tag_y[i] && y[i].connected.size() > 0)
                cout << " c" << i + 1;
        }

        cout << endl;
    }

    return 0;
}