朋友圈问题, quick_fond算法, 森林，并查集

本文主要是介绍朋友圈问题, quick_fond算法, 森林，并查集，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

​ 所谓一个朋友圈子，不一定其中的人都互相直接认识。
​ 例如：小张的朋友是小李，小李的朋友是小王，那么他们三个人属于一个朋友圈。
​ 现在给出一些人的朋友关系，人按照从 1到 n编号在这中间会进行询问某两个人是否属于一个朋友圈，请你编写程序，实现这个过程。

输 入

第一行输入两个整数 n,m(1≤n≤10000，3≤m≤100000)，分别代表人数和操作数。
接下来 m行，每行三个整 a,b,c（a∈[1,2], 1≤b,c≤n）当 a=1时，代表新增一条已知信息，b,c是朋友当 a=2
时，代表根据以上信息，询问 b,c是否是朋友

输 出

对于每个 a=2 的操作，输出『Yes』或『No』
代表询问的两个人是否是朋友关系。

样例输入

6 5
1 1 2
2 1 3
1 2 4
1 4 3
2 1 3

样例输出

No
Yes

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

typedef struct unionSet {
        int *color, n;
}UnionSet;

UnionSet *init(int n) {
        UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
        u->color = (int *)malloc(sizeof(int) * n);
        u->n = n;
        for (int i = 0; i < n; i++) u->color[i] = i;
        return u;
}

int fine(UnionSet *u, int n) {
        if (!u) return -1;
        return u->color[n];
}

int merge(UnionSet *u, int j1, int j2) {
        if (!u) return -1;
        int temp = u->color[j1];
        for (int i = 0; i < u->n; i++) u->color[i] - temp || (u->color[i] = u->color[j2]);
        return 1;
}

void clear(UnionSet *u) {
        if (!u) return ;
        free(u->color);
        free(u);
        return ;
}

int main() {
        int n, m, a, b, c;
        scanf("%d%d", &n, &m);
        UnionSet *u = init(n);
        for (int i = 0; i < m; i++) {
                scanf("%d%d%d", &a, &b, &c);
                --b, --c;
                a ^ 1 && printf("%s\n", fine(u, b) ^ fine(u, c) ? "No" : "Yes") || merge(u, b, c);
        }
        clear(u);
        return 0;
}

这篇关于朋友圈问题, quick_fond算法, 森林，并查集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！