首页 > 试题广场 >

并查集的实现

[编程题]并查集的实现
  • 热度指数:4228 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个没有重复值的整形数组arr,初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构,并提供以下两个操作。
  1. boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
  2. void union(int a, int b): 把a所在的集合与b所在的集合合并在一起,原本两个集合各自的元素以后都算作同一个集合
[要求]
如果调用isSameSet和union的总次数逼近或超过O(N),请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)

输入描述:
第一行两个整数N, M。分别表示数组大小、操作次数
接下来M行,每行有一个整数opt
若opt = 1,后面有两个数x, y,表示查询(x, y)这两个数是否属于同一个集合
若opt = 2,后面有两个数x, y,表示把x, y所在的集合合并在一起


输出描述:
对于每个opt = 1的操作,若为真则输出"Yes",否则输出"No"
示例1

输入

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

输出

No
Yes
Yes

说明

每次2操作后的集合为
({1}, {2}, {3}, {4})
({1}, {2, 3}, {4})
({1, 2, 3}, {4})

备注:

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

#define SWAP(a, b) { typeof(a) t = a; a = b; b = t; }

typedef enum { OK = 1, ERROR = -1 } Status;

const int N = 1E6;
int parents[N], ranks[N];

Status InitUnionFind(const int n) {
  int i;
  for (i = 1 ; i <= n; ++i) {
    *(parents + i) = i;
    *(ranks + i) = 1;
  }
  return OK;
}

// Path Compression
int Find(const int x) {
  if (*(parents + x) ^ x)
    *(parents + x) = Find(*(parents + x));
  return *(parents + x);
}

// Union by rank
void Union(int a, int b) {
  a = Find(a), b = Find(b);
  if (a == b) return;
  // a 始终指向秩小的树/集合/连通分量/簇的根或ID
  if (*(ranks + a) > *(ranks + b)) SWAP(a, b);
  
  *(parents + a) = b;
  if (*(ranks + a) == *(ranks + b))
    ++*(ranks + b);
}

int IsConnected(int a, int b) {
  return Find(a) == Find(b);
}

int main(const int argc, const char* const argv[]) {
  int n, m;
  fscanf(stdin, "%d %d", &n, &m);
  InitUnionFind(n);
  
  int op, a, b, i;
  while (m--) {
    fscanf(stdin, "%d %d %d", &op, &a, &b);
    if (op == 1) puts(IsConnected(a, b) ? "Yes" : "No");
    else         Union(a, b);
  }
  return 0;
}

发表于 2021-08-09 13:22:47 回复(0)
#include <bits/stdc++.h>
using namespace std;

int p[1000001];

int findParent(int x){
    return p[x]==x ? x : (p[x]=findParent(p[x]));
}

int main(){
    int n, m, opt, x, y;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        p[i] = i;
    while(m--){
        scanf("%d%d%d", &opt, &x, &y);
        if(opt==1){
            cout<<(findParent(x)==findParent(y)?"Yes":"No")<<endl;
        }else{
            int px=findParent(x), py=findParent(y);
            if(px<py){
                p[py] = px;
            }else if(px>py){
                p[px] = py;
            }
        }
    }
    return 0;
}

发表于 2020-04-06 03:22:14 回复(0)

一种比较简洁的实现并查集的方式

#include <cstdio>

using namespace std;

const int N = 1000010;
int p[N];
int n, m;

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) p[i] = i;
    while (m --)
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if ( t == 1)
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else p[find(a)] = find(b);
    }
    return 0;
}
发表于 2020-03-13 21:12:29 回复(0)
// 用scanf就过了,输入数据量太大,scanf和cin的差距就体现出来了

#include<iostream>
#include<vector>

using namespace std;

int findHead(vector<int>& arr, int val)
{
    int head = arr[val];
    if (head != val)
    {
        head = findHead(arr, head);
    }
    arr[val] = head;
    return head;
}

bool isSameSet(vector<int>& arr, int a, int b)
{
    return findHead(arr, a) == findHead(arr, b);
}

void unionSets(vector<int>& arr, vector<int>& rank, int a, int b)
{
    int aHead = findHead(arr, a);
    int bHead = findHead(arr, b);
    if (aHead != bHead)
    {
        if (rank[aHead] < rank[bHead])
        {
            arr[aHead] = bHead;
            rank[bHead] += rank[aHead];
        }
        else 
        {
            arr[bHead] = aHead;
            rank[aHead] += rank[bHead];
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> arr(n+1, 0);
    vector<int> rank(n+1, 1);
    for (int i=1; i<n+1; i++) arr[i] = i;
    int opt, x, y;
    while (m--)
    {
        //cin >> opt >> x >> y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1)
        {
            cout << (isSameSet(arr, x, y) ? "Yes" : "No") << endl;
        }
        else 
        {
            unionSets(arr, rank, x, y);
        }
    }
    return 0;
}

发表于 2019-10-16 19:05:42 回复(2)

这个时间是不是卡的太死了,为啥路径压缩了也过不了

import java.util.*;

public class Main {
    static int[] p;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        p = new int[n + 10];
        for (int i = 1; i <= n; i ++) {
            p[i] = i;
        }
        while (m -- > 0) {
            int o = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            if (2 == o) {
                p[find(a)] = find(b);
            } else {
                if (find(a) == find(b)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            }
        }
    }
    static int find(int x) {
        if (x != p[x]) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}
发表于 2021-01-30 21:59:40 回复(1)

我以前也不会呀,自从用了并查集之后,嗨,效果还真好!我们全家都用它!——某大佬

关于并查集,有以下题型:

  1. LeetCode130——Surrounded Regions——给了个二维 grid,把里面O全部变成X,但是边界和边界联通区域内的O保留(也能用DFS)
  2. LeetCode261——Graph Valid Tree——给了N个结点和一个边的集合,问这个边的集合能不能构成一棵树
  3. ...

并查集是一种树形数据结构,它由一个整型数组两种操作组成:

  1. 整型数组——记录每一个点对应前导点的下标
  2. find——确定元素属于哪一个子集,可以使用它来确定两个元素是否属于同一个子集
  3. union——将两个子集合并成一个集合

并查集的通用代码(看完你就明白这是个啥玩意儿了):

class UnionFind {
public:
    UnionFind (int sz) {
        pre = vector<int>(sz);
        for (int i = 0; i < sz; ++i) { pre[i] = i; }
    }

    // 查找根节点
    int find(int x) {
        int root = x;
        while (pre[root] != root) {
            root = pre[root];
        }
        // 路径压缩(降低时间复杂度)
        int start = x;
        while(pre[start] != root) {
            int tmp = pre[start];
            pre[start] = root;
            start = tmp;
        }
        return root;
    }

    // 合并子集
    void join(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) pre[rootY] = rootX;
    }

private:
    vector<int> pre;
};

图片如下

图片说明

基于上面👆并查集的框架,稍微修改一下,即可得到本题代码:

//
// Created by jt on 2020/9/7.
//
#include <vector>
#include <iostream>
using namespace std;

class UnionFind {
public:
    UnionFind (int sz) {
        pre = vector<int>(sz+1);
        for (int i = 1; i < sz; ++i) { pre[i] = i; }
    }

    // 查找根节点
    int find(int x) {
        int root = x;
        while (pre[root] != root) {
            root = pre[root];
        }
        // 路径压缩(降低时间复杂度)
        int start = x;
        while(pre[start] != root) {
            int tmp = pre[start];
            pre[start] = root;
            start = tmp;
        }
        return root;
    }

    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    // 合并子集
    void join(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) pre[rootY] = rootX;
    }

private:
    vector<int> pre;
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    for (int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) {
            if (uf.isSameSet(b, c)) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else {
            uf.join(b, c);
        }
    }
}
发表于 2020-09-07 10:41:42 回复(1)
本题考查并查集的实现,注意路径压缩,使用C++的朋友建议使用C风格的输入输出提高代码运行速度
#include <cstdio>
#include <vector>
using namespace std;

class UF{
private:
    int count;
    vector<int> parents;
    int find(int a)
    {
        if(parents[a] != a)
        {
            parents[a] = find(parents[a]);
        }
        int root = parents[a];
        return root;
    }
public:
    UF(int n)
    {
        this -> count = n;
        parents.resize(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            parents[i] = i;
        }
    }
    bool isSameSet(int a, int b)
    {
        int rootA = find(a);
        int rootB = find(b);
        if(rootA == rootB)
        return true;
        else
        return false;
    }
    void makeunion(int a, int b)
    {
        int rootA = find(a);
        int rootB = find(b);
        if(rootA != rootB)
        { 
            parents[rootA] = rootB;
            --count;
        }
    }
};
int main() {
    int N, M;
    //cin >> N >> M;        使用C风格的输入输出才能通过示例
    scanf("%d%d", &N, &M);
    UF uf(N);
    for(int i = 0; i < M; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(a == 1)
        {
            bool issame = uf.isSameSet(b, c);
            if(issame)
            printf("Yes\n");
            else
            printf("No\n") ;
        }
        else if(a == 2)
        uf.makeunion(b, c);
    }
    return 0;
}

发表于 2023-08-06 10:49:00 回复(0)
实现的时候使用rank来进行树高度的优化,能够提升查询速率
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < m; i++){
            params = br.readLine().split(" ");
            int opt = Integer.parseInt(params[0]), x = Integer.parseInt(params[1]), y = Integer.parseInt(params[2]);
            if(opt == 1)
                System.out.println(uf.isSameSet(x, y)? "Yes": "No");
            else
                uf.union(x, y);
        }
    }
}

class UnionFind {
    private int[] parent;         // 每个节点的父节点
    private int[] rank;           // 每个父节点的相对高度
    private int count;            // 连通分量数
    public UnionFind(int n) {
        count = n;
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    public int find(int x) {
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if(rank[rootX] > rank[rootY])          // rootY的子树更矮,将其合并到rootX的子树下
            parent[rootY] = rootX;
        else if(rank[rootX] < rank[rootY])     // rootX的子树更矮,将其合并到rootY的子树下
            parent[rootX] = rootY;
        else{
            // 否则无所谓谁合并到谁下边,不过此时需要更新树的高度
            parent[rootX] = rootY;
            rank[rootY] ++;
        }
        count--;
    }
    
    public boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    
    public int getCount() {
        return count;
    }
}

发表于 2021-11-13 20:27:37 回复(1)
java保存提交-:
    多行输出,例如System.out.println("somesth");会导致提示运行超时。垃圾!
发表于 2021-10-28 09:55:26 回复(0)

没想到fmt能这么慢

package main
import (
    "bufio"
    "os"
)
var in, out = bufio.NewReader(os.Stdin), bufio.NewWriter(os.Stdout)
func read() int {
    ret := 0
    for c, _ := in.ReadByte(); c >= '0' && c <= '9'; c, _ = in.ReadByte() {
        ret = (ret * 10) + int(c-'0')
    }
    return ret
}
func main() {
    var m, n int
    m,n = read(),read()
    // 创建并查集
    u := NewNowCoder(m)
    var opt, x, y int
    for i := 0; i < n; i++ {
        opt,x,y = read(),read(),read()
        if opt == 1 {
            if u.isSameSet(x, y) {
                out.WriteString("Yes\n")
            } else {
                out.WriteString("No\n")
            }
        } else {
            u.union(x, y)
        }
    }
    out.Flush()
}
type NowCoder struct {
    // 指向前面的节点(索引代表当前值,值代表父节点指针)
    father []int
    // 每个并查集的大小
    size []int
    // 记录寻找代表节点时沿途遇到的节点(帮助扁平化)
    stack []int
}
func NewNowCoder(l int) *NowCoder {
    res := &NowCoder{
        father: make([]int, l),
        size:   make([]int, l),
    }
    for i := 0; i < l; i++ {
        res.father[i] = i
        res.size[i] = 1
    }
    return res
}
// 查找某个值所在集合的代表节点
func (n *NowCoder) find(value int) int {
    for n.father[value] != value {
        // 将沿途节点添加到栈中
        n.stack = append(n.stack, value)
        value = n.father[value]
    }
    // 扁平化
    for i := 0; i < len(n.stack); i++ {
        n.father[n.stack[i]] = value
    }
    n.stack = make([]int, 0)
    return value
}
// 判断两个值是否在同一集合
func (n *NowCoder) isSameSet(v1, v2 int) bool {
    return n.find(v1) == n.find(v2)
}
// 合并两个元素所在的集合
func (n *NowCoder) union(v1, v2 int) {
    f1, f2 := n.find(v1), n.find(v2)
    // 小挂大
    if n.size[f1] > n.size[f2] {
        n.size[f1] += n.size[f2]
        n.father[f2] = f1
    } else {
        n.size[f2] += n.size[f1]
        n.father[f1] = f2
    }
}
发表于 2023-10-06 22:29:31 回复(0)
这个python优化的极致也过不了啊
发表于 2023-07-13 23:00:18 回复(0)
#include <iostream>
using namespace std;

int n,m;
const int N = 1000010;
int p[N];

int find(int x) {	//返回x的祖宗节点 + 路径压缩
	if (p[x] != x) p[x] = find(p[x]);//如果x不是根节点,就返回x的父节点(最终是根节点)
	return p[x];
}

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

	for (int i = 1; i < n; i++) p[i] = i;
while(m--){
	int opt[2];
	int a, b;
	scanf("%d%d%d", opt, &a, &b);

	if (opt[0] == 2) p[find(a)] = find(b);//合并操作
	else {
		if (find(a) == find(b)) puts("Yes");//如果祖宗节点一样,那么两个元素在同一个集合
		else puts("No");
	}
}
	return 0;
}写写模板
发表于 2022-09-11 21:04:30 回复(0)
这个题目主要是没办法使用Scanner作为输入,这个作为输入时间就会超出,借用一楼的思路终于找到了原因,有试过将记录节点信息的map换成数组,不加路径扁平化,结果都影响不大,最后终于找出来是输入函数的原因,感谢一楼大佬

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{ 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        UnionFindSet set = new UnionFindSet (n);
        for(int i=0; i< m; i++) {
            params = br.readLine().split(" ");
            int opt = Integer.parseInt(params[0]),
            a = Integer.parseInt(params[1]), 
            b = Integer.parseInt(params[2]);
            if(opt==1) {
                if(set.isSameSet(a,b)){
                    System.out.println("Yes");
                }
                else {
                    System.out.println("No");
                }
                
            }
            if(opt==2) {
                set.Union(a,b);
            }
        }  
    }
}

class UnionFindSet {
    private int[] fatherMap; //store the element's father
    private int[] rankMap; //store the set's rank
    public UnionFindSet(int N) {
        fatherMap = new int[N];
        rankMap = new int[N];
        for (int i = 0; i < N; i++) {
            fatherMap[i] =i;
            rankMap[i]=1;
        }
    }

    public int FindFather(int val) {
        int node=val;
        while (fatherMap[node] != node) {
            fatherMap[node]=fatherMap[fatherMap[node]];
            node = fatherMap[node];
        }

        return node;
    }

    public boolean isSameSet(int v1, int v2) {
        return FindFather(v1) == FindFather(v2);
    }
    public void Union(int v1, int v2) {

        int h1 = FindFather(v1);
        int h2 = FindFather(v2);
        if (h1 == h2) {
            return;
        }

        int rank1 = rankMap[h1];
        int rank2 = rankMap[h2];
        if (rank1 <= rank2) {
            fatherMap[h1]=h2;
            rankMap[h2]= rank1 + rank2;
            rankMap[h1]=-1;
        } else {
            fatherMap[h2]=h1;
            rankMap[h1]=rank1 + rank2;
            rankMap[h2]=-1;
        }
    }
}


发表于 2022-07-26 21:32:00 回复(0)
# UnionFind  并查集
# 连通分量: 自连接的点;
# 连通:自反性,等价性,传递性

class UnionFind(object):
    # 构造初始连通分量为N的并查集
    def __init__(self, N):
        self.count = N
        self.parent = [ i for i in range(N)]  # 每个节点的根节点
        self.weight = [1 for _ in range(N)]  # 以节点为根的树的节点个数
    
    # 连接p,q
    def union(self, p, q):
        rootp = self.find(p)
        rootq = self.find(q)
        if rootp == rootq:
            return
        # 小树接到大树下面
        if self.weight[rootq] > self.weight[rootp]:
            self.parent[rootp] = rootq
            self.weight[rootq] += self.weight[rootp]
        else:
            self.parent[rootq] = rootp
            self.weight[rootp] += self.weight[rootq]
        self.count -= 1
    
    # 找到p的根节点     
    def find(self, p):
        while self.parent[p] != p:
            self.parent[p] = self.parent[self.parent[p]]  # 压缩树的高度降低查找耗时
            p = self.parent[p]
        return p
    
    # 判断两个节点是否连接
    def connected(self, p, q):
        rootp = self.find(p)
        rootq = self.find(q)
        return rootp == rootq
    
    # 统计连通分量个数
    def count(self):
        return self.count

            

N, times = list(map(int, input().strip().split(' ')))
uf = UnionFind(N)
i = 0
res = ''
while i < times:
    i += 1
    op, n1, n2 = list(map(int, input().strip().split(' ')))
    if op == 1:
        res += 'Yes\n' if uf.connected(n1, n2) else 'No\n'
    elif op == 2:
        uf.union(n1, n2)
print(res)
发表于 2021-02-07 21:27:56 回复(0)
  • 贴一个Java的,使用压缩算法能避免超时
    • 看这个参考链接讲的比较清晰
    • find(x):record[x] = y,就相当于x的上级是y,一开始他们的上级都是自己,所以初始化record[x] = x;find(x)就是一直往上找x的最顶层的上级,找完之后压缩一下:把x以及x的非最顶层上级的直接上级都设置为找到的这个最顶层上级,这样下次寻找就不会费时,一次就找到
    • union(x, y):如果x和y的最顶层上级不是一个人,那么x和y不在一个集合里,就把y的最顶层上级设置为x的最顶层上级上级(record[fx] = fy)
import java.util.Scanner;
public class UnionFindSet {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        UnionFind unionFind = new UnionFind(N);
        for (int i = 0; i < M; i++) {
            int opt = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            if (opt == 1) {
                if (unionFind.isSameSet(x, y)) {
                    System.out.println("Yes");
                } else {
                    System.out.println("No");
                }
            } else {
                unionFind.union(x, y);
            }
        }
    }
    static class UnionFind {
        private int record[];
        UnionFind(int n) {
            record = new int[n];
            for (int i = 0; i < n; i++) {
                record[i] = i;
            }
        }
        public int find(int x) {
            int fx = x;
            while (fx != record[fx]) {
                fx = record[fx];
            }
            while (x != fx) {
                int temp = record[x];
                record[x] = fx;
                x = temp;
            }
            return fx;
        }
        public void union(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy) {
                record[fx] = fy;
            }
        }
        public boolean isSameSet(int x, int y) {
            int fx = find(x);
            int fy = find(y);
            return fx == fy;
        }
    }
}
发表于 2020-09-14 11:11:15 回复(2)
import java.util.*;

public class Main {

    public static int[] team;
    public static ArrayList<Integer> ac = new ArrayList<>();
    public static ArrayList<Integer> bc = new ArrayList<>();
    public static StringBuilder sb = new StringBuilder();

    public static int findRoot(int n) {
        return team[n] == n ? n : (team[n] = findRoot(team[n]));
    }

    public static void union(int a, int b) {
        int ra = findRoot(a);
        int rb = findRoot(b);
        if (ra < rb) {
            team[rb] = ra;
        } else if (ra > rb) {
            team[ra] = rb;
        }
    }

    public static void Qmsg(int a, int b) {
        for (int i = 0; i < ac.size(); ++i) {
            union(ac.get(i), bc.get(i));
        }
        sb.append(findRoot(a) == findRoot(b) ? "Yes\n" : "No\n");
        ac.clear();
        bc.clear();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m;
        n = sc.nextInt();
        m = sc.nextInt();
        team = new int[n + 1];
        for (int i = 0; i < n; i++) {
            team[i] = i;
        }
        int a,b,opt;
        for (int i = 0; i < m; ++i) {
            opt = sc.nextInt();
            a = sc.nextInt();
            b = sc.nextInt();
            if (opt == 1) {
                Qmsg(a, b);
            } else {
                ac.add(a);
                bc.add(b);
            }
        }
        System.out.println(sb);
        // TODO code application logic here
    }
}


发表于 2020-08-06 00:40:29 回复(0)
小白C语言版
#include<stdio.h>
#include<stdbool.h>

typedef struct node
{
    int rank;
    int parent;
}UFSTree;

void make_set (UFSTree *t, int n)
{
    int i;
    for (i = 0; i < n; ++i) {
        t[i].rank = 0;
        t[i].parent = i;
    }
}

int find_set (UFSTree *t, int x)
{
    if (t[x].parent == x)
        return x;
    return (find_set(t, t[x].parent));
}

bool is_same_set (UFSTree *t, int x, int y)
{
    x = find_set(t, x);
    y = find_set(t, y);
    
    if (x == y)
        return true;
    else 
        return false;
}

void myUnion (UFSTree *t, int x, int y)
{
    x = find_set(t, x);
    y = find_set(t, y);
    
    if (t[x].rank > t[y].rank) {
        t[y].parent = x;
    } else {
        t[x].parent = y;
        
        if (t[x].rank == t[y].rank)
            t[y].rank++;
    }
}



int main ()
{
    int n, m;
    scanf("%d %d", &n, &m);
    UFSTree t[n];
    make_set(t, n);
    
    int result[m], count = 0, opt, x, y;
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &opt, &x, &y);
        
        if (opt == 1) {
            
            if (is_same_set(t, x, y))
                result[count++] = 1;
            else 
                result[count++] = 0;
        
        } else if (opt == 2) {
            myUnion(t, x, y);
        }
    }
    
    for (int i = 0; i < count; ++i) {
        if (result[i]) {
            printf("%s\n", "Yes");
        } else {
            printf("%s\n", "No");
        }
    }
    
    return 0;
}


编辑于 2020-07-15 17:31:32 回复(0)
不能用map  查起来太耗时    所以一直通不过
#include "iostream"
#include  "vector"
#include  "stack"
#include  "map"
#include  "limits.h"
#include  "algorithm"
#include  "queue"
using namespace std;

int fathermap[1000001];
int randmap[1000001];
 
int findFather(int a)
{
   int f =  fathermap[a];
   if(f != a)
       f = findFather(f);
   fathermap[a] = f;
   return f;
}

bool isSameSet(int a, int b)
{
   int aFather = findFather(a);
   int bFather = findFather(b); 
   if(aFather == bFather)
       return true;
   return false;
}
 
void makeUnion(int a, int b)
{
    int small = randmap[findFather(a)] < randmap[findFather(b)] ? a : b;
    int big   = small == a ? b : a;
    randmap[big] += randmap[small];
    fathermap[fathermap[small]] = fathermap[big];   
}
 

 
int main()
{
    int N,M;
    cin>>N>>M;
     
    for(int i = 1; i <= N; i++)
    {
    	fathermap[i] = i;
    	randmap[i]   = 1;
    }
    
    int opt,a,b;
    while(M > 0)
    {
        cin>>opt>>a>>b;
        if(opt == 1)
        {
             if(isSameSet(a,b))
                 cout<<"Yes"<<endl;
             else
                 cout<<"No"<<endl;
        }
        else if(opt == 2)
        {
             makeUnion( a,  b);
        }
        M--;
    }
    return 0;
}

发表于 2020-05-21 11:01:52 回复(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL maxn = 10e6;
LL n,m;
LL f[maxn];

void init(){
    for(int i = 1; i <= n; i++)
        f[i] = i;
}

int findF(int v){
    if(f[v] == v)
        return v;
    else{
        int F = findF(f[v]);
        f[v] = F;
        return F;
    }
}

void merge(int u, int v){
    int t1 = findF(u);
    int t2 = findF(v);
    if(t1 != t2){
        f[t1] = t2;
    }
}
bool isSameSet(int u, int v){
    int t1 = findF(u);
    int t2 = findF(v);
    if(t1 != t2)
        return false;
    else
        return true;
       
}

int main(){
    LL flag,starx,stary;
    
    scanf("%lld%lld",&n,&m);
    init();
    for(int i = 1; i <= m; i++){
        scanf("%lld%lld%lld",&flag,&starx,&stary);
        switch(flag){
            case 1:
                if(isSameSet(starx,stary))
                    printf("Yes\n");
                else
                    printf("No\n");
                break;
            case 2:
                merge(starx,stary);
                break;
            default:
				break;
        }
    }
    return 0;
}

发表于 2020-03-10 22:03:37 回复(0)
40行哦
#include <bits/stdc++.h>
using namespace std;

int find(int x, int *f) {
	int res = f[x];
	if(res != x) {
		res = find(res, f);
	}
	f[x] = res;
	return res;
}

int main() {
	int n, m, opt, x, y;
	scanf("%d%d", &n, &m);
	int father[n], size[n];
	for(int i = 0; i < n; i++) {
		father[i] = i;
		size[i] = 1;
	}
	while(m--) {
		scanf("%d%d%d", &opt, &x, &y);
		x--; y--;
		if(opt == 1) {
			cout << (find(x, father) == find(y, father) ? "Yes" : "No") << endl;
		} else {
			int fx = find(x, father), fy = find(y, father);
			if(fx != fy) {
				if(size[fx] <= size[fy]) {
					father[fx] = fy;
					size[fy] += size[fx];
				} else {
					father[fy] = fx;
					size[fx] += size[fy];
				}
			}
		}
	}
	return 0;
}


发表于 2020-01-28 16:04:39 回复(0)