最大匹配(二分图和一般无向图)

二分图匈牙利算法

#include <bits/stdc++.h>

using namespace std;
const int SIZE = 1e5 + 10;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int n, m, tot;
bool visit[SIZE];
int match[SIZE];
int ans;

void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

bool dfs(int x) {
    for (int i = head[x]; i; i = Next[i]) {
        int y=ver[i];
        if (!visit[y]) {
            visit[y] = true;
            if (!match[y] || dfs(match[y])) {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for (int i = 1; i <= n; i++) {
        memset(visit, false, sizeof(visit));
        if (dfs(i)) {
            ans++;
            if (match[i])
                cout << i << ' ' << match[i] << endl;
        }
    }
    cout << ans;
    return 0;
}

input:
10 12
1 6
1 7
2 8
3 6
3 7
3 8
3 9
4 8
4 9
5 8
5 9
5 10
output:
6 1
7 3
8 2
9 4
10 5
10

一般无向图最大匹配(别人的代码)

#include <bits/stdc++.h>

using namespace std;

#define swap(x, y) {int tt=x;x=y;y=tt;}
const int N = 505 * 2;
const int M = 124750 * 2;
int f[N];
struct qq {
    int x, y;
    int last;
} s[M];
int num, last[N];
int n, m;

void init(int x, int y) {
    num++;
    s[num].x = x;
    s[num].y = y;
    s[num].last = last[x];
    last[x] = num;
}

int match[N];
int id[N];//这个点是什么点
//-1:没访问过  0:S点  1:T点
int q[N];//要扩展的队列————也就是我们要尝试帮谁换配偶
int pre[N];//在这次过程中,x的新配偶是谁
int Tim, vis[N];//对于lca的标记以及时间轴
int find(int x) {
    if (f[x] == x) return f[x];
    f[x] = find(f[x]);
    return f[x];
}

int lca(int x, int y)//寻找lca
{
    Tim++;
    while (vis[x] != Tim) {
        if (x != 0) {
            x = find(x);//先找到花根
            if (vis[x] == Tim) return x;
            vis[x] = Tim;
            if (match[x] != 0) x = find(pre[match[x]]);
                //因为在之前我们知道，每一个S点的配偶(也就是T点)的pre 都是指向他的父亲的,于是就直接这么跳就可以了
                //还有要注意的是，一定要先去到花根，因为他们现在已经是一个点了，只有花根的pre才指向他们真正的父亲
            else x = 0;
        }
        swap(x, y);
    }
    return x;
}

int st, ed;

void change(int x, int y, int k)//环  出现的是x---y的连边  已知根是k
{
    while (find(x) != k) {
        pre[x] = y;
        int z = match[x];
        id[z] = 0;
        q[ed++] = z;
        if (ed >= N - 1) ed = 1;
        if (find(z) == z) f[z] = k;
        if (find(x) == x) f[x] = k;
        y = z;
        x = pre[y];
    }
}

void check(int X)//尽量帮助x寻找增广路
{
    for (int u = 1; u <= n; u++) {
        f[u] = u;
        id[u] = -1;
    }
    st = 1;
    ed = 2;
    q[st] = X;
    id[X] = 0;
    while (st != ed) {
        int x = q[st];
        for (int u = last[x]; u != -1; u = s[u].last) {
            int y = s[u].y;
            if (match[y] == 0 && y != X)
                //当然match[X]=0,但X(这次来寻找配偶的点)并不是一个可行的东西,所以不能算可行解
            {
                pre[y] = x;//先假设他与x相连
                int last, t, now = y;
                while (now != 0)//当然，这次来的X的match是为0，要是能更新到0就是结束
                {
                    t = pre[now];//now新的配偶
                    last = match[t];//理所当然啦
                    match[t] = now;
                    match[now] = t;
                    now = last;
                }
                return;
            }
            if (id[y] == -1)//找到一个没有访问过的点————进行扩展
            {
                id[y] = 1;
                pre[y] = x;//先假设他与x相连
                id[match[y]] = 0;
                q[ed++] = match[y];
                if (ed >= N - 1) ed = 1;
            } else if (id[y] == 0 && find(x) != find(y))//出现一个以前未处理过的奇环
            {
                int g = lca(x, y);
                change(x, y, g);
                change(y, x, g);
            }
        }
        st++;
        if (st >= N - 1) st = 1;
    }
}

int main() {
    memset(vis, 0, sizeof(vis));
    Tim = 0;
    memset(match, 0, sizeof(match));
    num = 0;
    memset(last, -1, sizeof(last));
    scanf("%d%d", &n, &m);
    for (int u = 1; u <= m; u++) {
        int x, y;
        scanf("%d%d", &x, &y);
        init(x, y);
        init(y, x);
    }
    for (int u = 1; u <= n; u++)
        if (match[u] == 0)
            check(u);
    int ans = 0;
    for (int u = 1; u <= n; u++)
        if (match[u] != 0) ans++;
    set<int> remain;
    for (int i = 1; i <= n; i++)
        remain.insert(i);
    while (!remain.empty()) {
        int i = *(remain.begin());
        if (match[i] != 0)
            printf("%d %d\n", i, match[i]);
        remain.erase(i);
        remain.erase(match[i]);
    }
    printf("%d\n", ans);
    return 0;
}

input:
10 12
1 6
1 7
2 8
3 6
3 7
3 8
3 9
4 8
4 9
5 8
5 9
5 10
output:
1 7
2 8
3 6
4 9
5 10
10