求一个一般图最大匹配(带花树算法)的c语言版本

Question

C＋＋基础太薄弱了，希望大佬能写个c语言版本的，估计才有看懂的可能性。😭

Answer 1

一般图最大匹配问题是指在一个无向图中找到一个由边组成的集合，其中任意两条边均无公共顶点，并且该集合的大小尽可能大。带花树算法是一种求解一般图最大匹配问题的经典算法之一，下面是带花树算法的C语言实现：

```c
#include <stdio.h>
#include <string.h>
#define MAXN 1000

int n, m;
int match[MAXN], fa[MAXN];
int mark[MAXN], stk[MAXN], top;
bool g[MAXN][MAXN];

int find(int u) {
    int d = u;
    while (d != fa[d]) {
        d = fa[d];
    }
    int p, tmp;
    while (u != d) {
        p = fa[u];
        fa[u] = d;
        tmp = match[u];
        match[u] = match[p];
        match[p] = tmp;
        u = p;
    }
    return d;
}

void blossom(int u, int v, int t) {
    while (1) {
        u = find(u);
        mark[u] = t;
        if (!match[u]) {
            break;
        }
        v = match[u];
        mark[v] = t;
        u = stk[top--] = fa[v];
    }
    if (u) {
        for (int i = 1; i <= n; i++) {
            if (mark[i] == t && g[u][i]) {
                fa[i] = u;
                stk[++top] = i;
            }
        }
    }
}

bool dfs(int u) {
    for (int i = 1; i <= n; i++) {
        if (g[u][i] && fa[u] != fa[i]) {
            if (match[i]) {
                fa[i] = u;
                if (dfs(match[i])) {
                    return true;
                }
            } else {
                int d = u, p = i, v;
                while (d != fa[d]) {
                    stk[++top] = d;
                    v = match[d];
                    mark[d] = 1;
                    mark[v] = 1;
                    g[d][v] = g[v][d] = 1;
                    d = fa[d];
                }
                stk[++top] = d;
                mark[d] = 1;
                g[d][p] = g[p][d] = 1;
                match[p] = d;
                while (top) {
                    blossom(stk[top], p, 0);
                    blossom(stk[top--], p, 0);
                }
                return true;
            }
        }
    }
    return false;
}

int max_match() {
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (!match[i]) {
            top = 0;
            if (dfs(i)) {
                match[i] = -1;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += (match[i] > 0);
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = 1;
    }
    int ans = max_match();
    printf("%d\n", ans);
    return 0;
}

其中，match[i]表示顶点i匹配的点的编号，如果match[i] = 0，则表示该点未被匹配，match[i] > 0表示该点被匹配到了编号为match[i]的点，match[i] < 0表示该点被标记为“花朵”（下文会讲到），-match[i]表示与该花朵匹配的点。

fa[i]表示顶点i在并查集中的父亲节点，stk数组是辅助数组，用于保存花朵的一些信息，mark数组表示当前图中与某个点相连的边是否在花朵中，g[i][j]为真表示顶点i和顶点j之间有边相连。
find()函数实现的是路径压缩的并查集。
blossom()函数实现了从顶点u到顶点v的路径上所有非匹配边构成的花朵的收缩操作。
dfs()函数实现了从顶点u开始的增广路查找，并在找到增广路时将对应的匹配边进行调整，如果找不到增广路则返回false。
max_match()函数实现了求解最大匹配的主体程序，其中遍历每个未匹配的点，尽可能将该点匹配到一个未被匹配的点上，如果找到增广路则将对应的匹配关系进行调整。
最终输出的答案就是最大匹配的大小。
希望对您有所帮助！

以下是C++版本，可以对应看一下：

```c++
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

int n, m;
int match[MAXN], fa[MAXN];
int mark[MAXN], stk[MAXN], top;
bool g[MAXN][MAXN];

int find(int u) {
    int d = u;
    while (d != fa[d]) {
        d = fa[d];
    }
    int p, tmp;
    while (u != d) {
        p = fa[u];
        fa[u] = d;
        tmp = match[u];
        match[u] = match[p];
        match[p] = tmp;
        u = p;
    }
    return d;
}

void blossom(int u, int v, int t) {
    while (1) {
        u = find(u);
        mark[u] = t;
        if (!match[u]) break;
        v = match[u];
        mark[v] = t;
        u = stk[++top] = fa[v];
    }
    if (u) {
        for (int i = 1; i <= n; i++) {
            if (mark[i] == t && g[u][i]) {
                fa[i] = u;
                stk[++top] = i;
            }
        }
    }
}

bool dfs(int u) {
    for (int i = 1; i <= n; i++) {
        if (g[u][i] && fa[u] != fa[i]) {
            if (match[i]) {
                fa[i] = u;
                if (dfs(match[i])) return true;
            } else {
                int d = u, p = i, v;
                while (d != fa[d]) {
                    stk[++top] = d;
                    v = match[d];
                    mark[d] = 1;
                    mark[v] = 1;
                    g[d][v] = g[v][d] = 1;
                    d = fa[d];
                }
                stk[++top] = d;
                mark[d] = 1;
                g[d][p] = g[p][d] = 1;
                match[p] = d;
                while (top) {
                    blossom(stk[top], p, 0);
                    blossom(stk[top--], p, 0);
                }
                return true;
            }
        }
    }
    return false;
}

int max_match() {
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (!match[i]) {
            top = 0;
            if (dfs(i)) {
                match[i] = -1;
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += (match[i] > 0);
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = 1;
    }
    int ans = max_match();
    printf("%d\n", ans);
    return 0;
}