#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;
}

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

#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;
}

// 用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;
}

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

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];
    }
}

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

关于并查集，有以下题型：

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);
        }
    }
}

#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;
}

#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;
}

迭代版

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

const int MAXN = 1e6 + 1;
int father[MAXN];
int cnt[MAXN];
int st[MAXN];
int n;

//初始化并查集
void build() {
    for (int i = 0; i < n + 1; i++) {
        father[i] = i;
        cnt[i] = 1;
    }
}

//寻找代表节点&&压缩路径
int find(int i) {
    int size = 0;
    while (i != father[i]) {
        st[size++] = i;
        i = father[i];
    }
    while (size > 0) {
        father[st[--size]] = i;
    }
    return i;
}

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

void unionSet(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        if (cnt[fx] >= cnt[fy]) {
            cnt[fx] += cnt[fy];
            father[fy] = fx;
        } else {
            cnt[fy] += cnt[fx];
            father[fx] = fy;
        }
    }
}



int main() {
    int m;
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> m) {
        build();
        for (int i = 0; i < m; i++) {
            int opt, x, y;
            cin >> opt >> x >> y;
            if (opt == 1) {
                cout << (isSamSet(x, y) ? "Yes" : "No" ) << endl;
            } else {
                unionSet(x, y);
            }
        }

    }
    return 0;
}

递归版

#include <iostream>
using namespace std;
const int MAXN = 1e6 + 1;
int father[MAXN];
int n;

// 初始化父节点
void build() {
    for (int i = 0; i < n + 1; i++) {
        father[i] = i;
    }
}

// 查找代表节点并进行路径压缩
int find(int i) {
    if (i != father[i]) {
        father[i] = find(father[i]);
    }
    return father[i];
}

// 判断两个节点是否在同一集合
bool isSameSet(int x, int y) {
    return find(x) == find(y);
}

// 合并两个集合
void unionSet(int x, int y) {
    father[find(x)] = find(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;
    while (cin >> n >> m) {
        build();
        for (int i = 0; i < m; i++) {
            int opt, x, y;
            cin >> opt >> x >> y;
            if (opt == 1) {
                cout << (isSameSet(x, y) ? "Yes" : "No") << endl;
            } else {
                unionSet(x, y);
            }
        }
    }
    return 0;
}

import java.io.*;

public class Main {
    // 经典并查集

    public static int MAXN = 1000001;
    public static int[] father = new int[MAXN];
    public static int[] size = new int[MAXN];
    public static int[] stack = new int[MAXN];
    public static int n;

    public static void build() {
        for (int i = 0; i <= n; ++i) {
            father[i] = i;
            size[i] = 1;
        }
    }

    // i 号节点一直往上查，找到代表节点
    public static int find(int i) {
        int size = 0; // 沿途收集了多少个节点

        // 扁平化
        while (i != father[i]) {
            stack[size++] = i; // i 收集起来
            i = father[i]; // i 往上跳
        }
        // 沿途节点收集好，i 已经跳到代表节点
        while (size > 0) {
            father[stack[--size]] = i;
        }
        return i;
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        // 小挂大优化
        if (fx != fy) {
            // fx, fy 代表大小
            if (size[fx] >= size[fy]) {
                size[fx] += size[fy];
                father[fy] = fx;
            } else {
                size[fy] += size[fx];
                father[fx] = fy;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            build();
            int m = (int) in.nval;
            for (int i = 0; i < m; ++i) {
                in.nextToken();
                int op = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                in.nextToken();
                int y = (int) in.nval;
                if (op == 1) {
                    out.println(isSameSet(x, y) ? "Yes" : "No");
                } else {
                    union(x, y);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

没想到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
    }
}

#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;
}写写模板

• 贴一个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;
        }
    }
}

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
    }
}

不能用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;
}