C语言求某社交网络中共有 n 个人，即a1,a2,…,an。当给定 n，以及部分人际关系。为扩展人际关系，可利用已有的人际关系来认识一些不识之人，若只通过一人的牵线，试问哪些人员之间可间接建立起人际关系。 算法： 输入描述： n, (a1, a2), (a1, a3), …, (ai, aj) 例如，5, (1, 2), (1, 3), (1, 4), (2, 5), (3, 4） 输出描述：(ai,aj)…(ak, al) 要求：各括号对的输出要求保证按按字典序或自然数递增排序。例如，(1,5)(2,3

), (1,5)(2,4), (1,5)(3,4), (2,5)(3,4)。

算法实现：

首先，我们可以通过邻接表来存储人际关系，将人际关系转换成图的形式。然后，我们可以使用深度优先搜索或广度优先搜索算法来查找所有的间接人际关系。

具体步骤如下：

1. 根据输入构建邻接表，存储人际关系。

2. 对于每个人 a，使用深度优先搜索或广度优先搜索算法，查找所有与 a 相连的人 b，并标记已经访问过的人。

3. 对于每个已经访问过的人 b，再使用深度优先搜索或广度优先搜索算法，查找所有与 b 相连的人 c，并标记已经访问过的人。

4. 重复步骤 3，直到找到所有的间接人际关系。

5. 将所有的间接人际关系按字典序或自然数递增排序后输出。

C++代码实现如下：

相关问题

某社交网络中共有n个人即a1，a2，到an给定n，以及部分人际关系。为扩展人际关系，可利用已有的人际关系来认识一些不识之人，若只通过一人的牵线，试间哪些人员之间可间接建立起人际关系。c语言

这个问题可以用图论中的深度优先搜索(DFS)或广度优先搜索(BFS)算法来解决。我们可以把人际关系看作是一个无向图，每个人是图中的一个节点，人与人之间的关系是边。

具体实现方法如下：

1. 定义一个邻接矩阵来表示人际关系图，矩阵的第i行第j列元素为1表示第i个人和第j个人之间有人际关系，否则为0。

2. 选择一个起点人，将起点人的所有直接连接的人标记为已访问过的。

3. 遍历起点人的所有已访问过的直接连接的人，将它们的直接连接的人标记为已访问过的。

4. 递归地遍历已访问过的人的直接连接的人，直到遍历完所有已访问过的人的直接连接的人。

5. 遍历完所有已访问过的人的直接连接的人后，所有与起点人有人际关系的人都已被标记为已访问过，即可输出所有与起点人有人际关系的人。

下面是一个简单的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100 // 最大人数

int n; // 人数
int graph[MAXN][MAXN]; // 邻接矩阵
int visited[MAXN]; // 是否已访问

void dfs(int v) { // 深度优先遍历
    visited[v] = 1;
    printf("%d ", v);
    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {
            dfs(i);
        }
    }
}

void bfs(int v) { // 广度优先遍历
    int queue[MAXN], front = 0, rear = 0; // 队列
    visited[v] = 1;
    printf("%d ", v);
    queue[rear++] = v;
    while (front < rear) {
        int u = queue[front++];
        for (int i = 0; i < n; i++) {
            if (graph[u][i] && !visited[i]) {
                visited[i] = 1;
                printf("%d ", i);
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    // 输入人数和人际关系
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    // 搜索与第1个人有人际关系的人
    printf("DFS: ");
    dfs(0);
    printf("\n");
    // 初始化visited数组
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    // 搜索与第1个人有人际关系的人
    printf("BFS: ");
    bfs(0);
    printf("\n");
    return 0;
}

以上代码中，我们分别实现了深度优先遍历和广度优先遍历两种搜索算法。其中，dfs函数是深度优先遍历函数，bfs函数是广度优先遍历函数，visited数组用于标记每个节点是否已访问过。在主函数中，我们首先输入人数和人际关系，然后调用dfs和bfs函数输出与第1个人有人际关系的人。

C语言代码求某社交网络中共有 n 个人，即a1,a2,…,an。当给定 n，以及部分人际关系。为扩展人际关系，可利用已有的人际关系来认识一些不识之人，若只通过一人的牵线，试问哪些人员之间可间接建立起人际关系。 算法： 输入描述： n, (a1, a2), (a1, a3), …, (ai, aj) 例如，5, (1, 2), (1, 3), (1, 4), (2, 5), (3, 4） 输出描述：(ai,aj)…(ak, al) 要求：各括号对的输出要求保证按按字典序或自然数递增排序。

以下是 C 语言代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1000

int graph[MAXN][MAXN];
int visited[MAXN];
int n;

void dfs(int u, int* count, int* res) {
    visited[u] = 1;
    for (int v = 1; v <= n; v++) {
        if (graph[u][v] && !visited[v]) {
            res[*count] = (u < v) ? (u * 1000 + v) : (v * 1000 + u);
            (*count)++;
            dfs(v, count, res);
        }
    }
}

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int main() {
    scanf("%d", &n);

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

    int a, b;
    for (int i = 0; i < m; i++) {
        scanf("(%d,%d)", &a, &b);
        graph[a][b] = graph[b][a] = 1;
    }

    int count = 0;
    int* res = (int*)malloc(sizeof(int) * MAXN);
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i, &count, res);
        }
    }

    qsort(res, count, sizeof(int), cmp);

    for (int i = 0; i < count; i++) {
        printf("(%d,%d)%c", res[i] / 1000, res[i] % 1000, i == count-1 ? '\n' : ' ');
    }

    free(res);

    return 0;
}

输入格式为：

n
m
(a1,b1)
(a2,b2)
...
(am,bm)

其中 n 表示人员数量，m 表示人际关系数目，后面的 ai 和 bi 表示两个人之间存在人际关系。输出的格式为：

(ai,aj)...(ak,al)

表示这些人之间存在间接人际关系，且按字典序或自然数递增排序。