使用并查集判断图连通性

并查集,英文名称Disjoint-set data structure

在計算機科學中，併查集（英文：Disjoint-set data structure，直譯為不交集數據結構）是一種數據結構，用於處理一些不交集（Disjoint sets，一系列沒有重複元素的集合）的合併及查詢問題。併查集支持如下操作：

判断依据

图联通,则所有节点具有相同的根节点

题目

使用并查集判断图连通性

输入

本问题有多组测试数据，每组测试数据有两部分，第一部分只有一行，是两个正整数，分别表示图的节点数N（节点编号从1到N，1<=N<=100）和图的边数E；第二部分共有E行，每行也是两个整数N1，N2（1<=N1，N2<=N），分别表示N1和N2之间有一条边。

输出

Yes
No

数据结构

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;

初始化

让所有节点的根节点都为她自己

UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        // 使用 std::iota 初始化 parent 数组
        iota(parent.begin(), parent.end(), 0);
}

并查集find操作

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

这里用到了路径压缩,将所有根节点下的节点变成兄弟节点,树呈两层

并查集的合并操作

void unite(int x, int y) {
  int rootX = find(x);
  int rootY = find(y);

  // 这里用到了按秩合并,优化查询的时间开销
  if (rootX != rootY) {
      if (rank[rootX] < rank[rootY]) {
          parent[rootX] = rootY;
      }
      else if (rank[rootX] > rank[rootY]) {
          parent[rootY] = rootX;
      }
      else {
          parent[rootY] = rootX;
          rank[rootX]++;
      }
  }
}

判断是否联通

bool isConnected(int n, const vector<pair<int, int>>&edges) {
    UnionFind uf(n);
    for (int i = 1; i <= edges.size() - 1; i++) {
        int a = edges[i].first;
        int b = edges[i].second;
        uf.unite(a, b);
    }
    int root = uf.find(1);
    for (int i = 1; i <= n; i++) {
        if (uf.find(i) != root) {
            return false;
        }
    }
    return true;
}

完整代码(better c++ 14 and than)

#ifndef STDHPP
#define STDHPP

#ifdef compiler_directive
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "ofast", "inline")
#endif

#ifndef headfile
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <unordered_set>
#include <regex>
#endif

#ifndef macro_definition
#define _SILENCE_CXX20_CISO646_REMOED_WARNING
#define fspr(n) fixed << setprecision(n)
#define spr(n) setprecision(n)
#define sci setiosflags(ios::scientific)
#define siosf setiosflags
#define fspr(n) fixed << setprecision(n)
#define spr(n) setprecision(n)
#define sci setiosflags(ios::scientific)
#define siosf setiosflags
#define ifor(i, l, r) for (int i = l; i <= r; ++i)
#define rfor(i, r, l) for (int i = r; i >= l; --i)
#define npos string::npos
#define fir first
#define sec second
#define pb push_back
#define pf push_front
#define inlast(a) a.size() - 1
#define itlast(a) prev(a.end(), 1)
#define all(v) v.begin(), v.end()
#endif

#ifndef usenamespace
// using namespace std;
#endif

#ifndef type_alias
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long long ull;
typedef long double doubleL;
template<class T, class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>>
using priqueue = std::priority_queue<T, Container, Compare>;
#endif

#ifndef customized_namespace
namespace cus {
    // standard output
    template<typename container>
    void print(container&a2) {
        for (auto i = a2.begin(); i != a2.end(); i++) {
            std::cout << *i << " \n"[i == prev(a2.end(), 1)];
        }
    }

    template<typename T1>
    auto print(T1 a, i64 l, i64 r) -> void {
        for (long i = l; i <= r; ++i) {
            std::cout << a[i] << " /n"[i == r];
        }
    }

    //__int128 write
    template<typename T>
    void read(T&w) {
        w = 0;
        T f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                f = -1;
            ch = getchar();
        }
        while (ch <= '9' && ch >= '0') {
            w = w * 10 + ch - '0';
            ch = getchar();
        }
    }

    template<typename T>
    void print128(T x) {
        if (x < 0) {
            putchar('-');
        }
        x = -x;
        if (x > 9)
            print128(x / 10);
        putchar(x % 10 + '0');
    }
} // namespace cus
#endif

#ifndef constant
constexpr int I_INF = 0x3f3f3f3f;
constexpr long L_INF = 0x3f3f3f3f3f3f3f3f;
constexpr double EPS = 1.0e-9;
constexpr long MOD = 1e9 + 7;
constexpr int N = 1e2 + 10;
constexpr double d_INF = std::numeric_limits<double>::infinity();
constexpr long long LL_INF = std::numeric_limits<i64>::infinity();
#endif

#ifndef global_variable
#endif

#endif
using namespace std;
class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n + 1);
        rank.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        // 路径压缩,将根节点下的所有节点都变成兄弟节点两层
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }


    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            }
            else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            }
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

bool isConnected(int n, const vector<pair<int, int>>&edges) {
    UnionFind uf(n);
    for (int i = 1; i <= edges.size() - 1; i++) {
        int a = edges[i].first;
        int b = edges[i].second;
        uf.unite(a, b);
    }
    int root = uf.find(1);
    for (int i = 1; i <= n; i++) {
        if (uf.find(i) != root) {
            return false;
        }
    }
    return true;
}

vector<pair<int, int>> edges;

int main() {
    int n, m;
    while (cin >> n >> m) {
        edges.resize(m + 1);
        for (int i = 1; i <= m; i++) {
            cin >> edges[i].first >> edges[i].second;
        }
        bool connected = isConnected(n, edges);
        if (connected) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
        edges.clear();
    }
    return 0;
}