C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int sz = 500010;
const int inf = 0x3f3f3f3f;
int head[sz], nxt[sz * 2], to[sz * 2], w[sz];
int low[sz], dfn[sz], Stack[sz]; int ext[sz];
int ds[sz]; int cur[sz]; int c[sz];
vector<int >dcc[sz];
int n, m, t; int num = 0, cnt = 0, top = 0;
int tot = 1; int s, T;
void add(int x, int y, int z){
    to[++tot] = y;
    w[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
bool bfs(int x){
    memset(ds, 0, sizeof ds);
    ds[x] = 1;
    queue<int >q;
    q.push(x);
    while (q.size()){
        int p = q.front();
        q.pop();
        for (int i = head[p]; i; i = nxt[i]){
            int t = to[i];
            if (!ds[t] && w[i]){
                ds[t] = ds[p] + 1;
                q.push(t);
            }
        }
    }
    return ds[T] != 0;
}
int dfs(int x, int flw){
    if (x == T)return flw;
    int detal = flw;
    for (int &i = cur[x]; i; i = nxt[i]){
        int t = to[i];
        if (ds[t] != ds[x] + 1 || w[i] <= 0)continue;
        int d = dfs(t, min(w[i], detal));
        w[i] -= d, w[i ^ 1] += d;
        detal -= d;
        if (detal == 0)break;
    }
    return flw - detal;
}
int dinic(){
    int res = 0;
    while (bfs(s)){
        for (int i = 1; i <= n; i++)cur[i] = head[i];
        res += dfs(s, inf);
    }
    return res;
}
void tarjan(int x){
    low[x] = dfn[x] = num++;
    Stack[++top] = x;
    ext[x] = 1;
    for (int i = head[x]; i; i = nxt[i]){
        int t = to[i];
        if (!w[i])continue;
        if (!dfn[t]){
            tarjan(t);
            low[x] = min(low[x], low[t]);
        }
        else if (ext[t]){
            low[x] = min(low[x], dfn[t]);
        }
    }
    if (dfn[x] == low[x]){
        int y; cnt++;
        do{
            y = Stack[top--];
            dcc[cnt].push_back(x);
            ext[y] = 0;
            c[y] = cnt;
        } while (x != y);
    }
}
int main(){
    //freopen("C:/Users/MC/Desktop/1.txt", "r", stdin);
    cin >> n >> m >> t;
    int x, y;
    for (int i = 1; i <= t; i++){
        scanf("%d%d", &x, &y);
        y = n + y;
        add(x, y, 1);
        add(y, x, 0);
    }
    s = n + m + 1;
    T = n + m + 2;
    for (int i = 1; i <= n; i++){
        add(s, i, 1);
        add(i, s, 0);
    }
    for (int i = n + 1; i <= n + m; i++){
        add(i, T, 1);
        add(T, i, 0);
    }
    n = n + m + 2;
    dinic();
    for (int i = 1; i <= n; i++){
        if (!dfn[i])tarjan(i);
    }
    vector<int > ans;
    for (int i = 2; i <= 2 * t + 1; i += 2){
        int u = to[i ^ 1]; int v = to[i];
        if (w[i] == 1 && c[u] != c[v]){
            ans.push_back(i);
        }
    }
    int len = ans.size();
    cout << len << endl;;
    for (int i = 0; i < len; i++){
        printf("%d", ans[i] / 2);
        if (i != len - 1)putchar(' ');
    }
    putchar('\n');
    return 0;
}