Cặp ghép cực đại trên đồ thị hai phía

Bài toán

Tìm cặp ghép cực đại trên đồ thị hai phía không trọng số.

Độ phức tạp

O(n2)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 102;

int n, m, Assigned[N];

int Visited[N], t = 0;

vector<int> a[N];

bool visit(int u) {

    if (Visited[u] != t)

        Visited[u] = t;

    else

        return false;

    for (int i = 0; i < a[u].size(); i++) {

        int v = a[u][i];

        if (!Assigned[v] || visit(Assigned[v])) {

            Assigned[v] = u;

            return true;

        }

    }

    return false;

}

int main() {

    scanf("%d%d", &m, &n);

    int x, y;

    while (scanf("%d%d", &x, &y) > 0)

        a[x].push_back(y);

    int Count = 0;

    for (int i = 1; i <= m; i++) {

        t++;

        Count += visit(i);

    }

    printf("%d\n", Count);

    for (int i = 1; i <= n; i++)

        if (int j = Assigned[i])

            printf("%d %d\n", j, i);

}

Nhận xét

Code này đã được dùng để nộp cho một bài trên SPOJ.

Tham khảo

http://vn.spoj.com/problems/MATCH1/

https://codeforces.com/group/FLVn1Sc504/contest/274505/problem/C