C语言实现情侣配对算法 - 朋友的朋友一定是朋友 - 常规

C语言实现情侣配对算法 - 朋友的朋友一定是朋友

题目描述

有两个公司 A 和 B，每个公司的员工都是同性。

A 公司有 N 名员工，其中有 P 对朋友关系。B 公司有 M 名员工，其中有 Q 对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数 (Xi, Yi) 组成，表示朋友的编号分别为 Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是 1，小红的编号是 -1.

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入格式

第 1 行，4 个空格隔开的正整数 N, M, P, Q。

之后 P 行，每行两个正整数 Xi，Yi。

之后 Q 行，每行两个负整数 Xi，Yi。

输出格式

一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出样例

说明/提示

对于 30% 数据，N, M <= 100，P, Q <= 200
对于 80% 数据，N, M <= 4000, P, Q <= 10000.
对于全部数据，N, M <= 10000, P, Q <= 20000。

C语言代码

#include <stdio.h>
#include <stdlib.h>
#define MAXN 10000

int n, m, p, q;
int a[MAXN + 1][MAXN + 1]; // A 公司朋友关系矩阵
b[MAXN + 1][MAXN + 1]; // B 公司朋友关系矩阵
int vis[MAXN + 1]; // 标记是否已经配对

void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = 0;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] = 0;
        }
    }
}

void add_edge(int x, int y, int type) {
    if (type == 1) { // A 公司
        a[x][y] = a[y][x] = 1;
    } else { // B 公司
        b[x][y] = b[y][x] = 1;
    }
}

int dfs(int u) {
    for (int v = 1; v <= n + m; v++) {
        if (vis[v] == 0 && ((u <= n && v <= n && a[u][v] == 1) || (u > n && v > n && b[u - n][v - n] == 1))) {
            vis[v] = 1;
            if (dfs(v)) {
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    scanf('%d %d %d %d', &n, &m, &p, &q);
    init();

    // 读取朋友关系
    int x, y;
    for (int i = 0; i < p; i++) {
        scanf('%d %d', &x, &y);
        add_edge(x, y, 1);
    }
    for (int i = 0; i < q; i++) {
        scanf('%d %d', &x, &y);
        add_edge(x, y, 2);
    }

    // 小明和小红是朋友
    add_edge(1, -1, 2);

    // 深度优先搜索
    int ans = 0;
    vis[1] = 1;
    vis[-1] = 1;
    ans += dfs(-1);
    ans += dfs(1);

    printf('%d\n', ans);
    return 0;
}

算法思路

使用邻接矩阵存储朋友关系，分别记录 A 公司和 B 公司的 friend 关系。
从小明和小红开始，使用深度优先搜索 (DFS) 遍历所有与他们相连的朋友，并记录已配对的节点。
在 DFS 过程中，如果找到一个未配对的异性朋友，则配对成功，并返回 1，表示找到一对情侣。
统计所有配对成功的次数，即为最终答案。

代码解释

init() 函数初始化邻接矩阵。
add_edge() 函数添加朋友关系。
dfs() 函数实现深度优先搜索，寻找未配对的异性朋友。
main() 函数读取输入数据，调用 dfs() 函数进行搜索，并输出结果。

注意

代码中将 B 公司的编号加上 n，以便与 A 公司的编号区分。
由于朋友关系是双向的，因此在添加朋友关系时需要同时添加两条边。
在 DFS 过程中，需要判断当前节点是否已经配对，以及当前节点和目标节点是否为异性。

优化建议

可以使用并查集优化朋友关系的存储，以减少空间复杂度。
可以使用更高级的图论算法，例如匈牙利算法，来寻找最大匹配。