不相交的集合数据结构

// Finds the representative of the set
// that i is an element of

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

int find(int i)

{

	// If i is the parent of itself
	if (parent[i] == i) {

		// Then i is the representative of
		// this set
		return i;
	}
	else {

		// Else if i is not the parent of
		// itself, then i is not the
		// representative of his set. So we
		// recursively call Find on its parent
		return find(parent[i]);
	}
}

// The code is contributed by Nidhi goel

// Unites the set that includes i
// and the set that includes j

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

void union(int i, int j) {

	// Find the representatives
	// (or the root nodes) for the set
	// that includes i
	int irep = this.Find(i),

	// And do the same for the set
	// that includes j
	int jrep = this.Find(j);

	// Make the parent of i’s representative
	// be j’s representative effectively
	// moving all of i’s set into j’s set)
	this.Parent[irep] = jrep;
}

// Unites the set that includes i and the set
// that includes j

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

void union(int i, int j) {

	// Find the representatives (or the root nodes)
	// for the set that includes i
	int irep = this.find(i);

	// And do the same for the set that includes j
	int jrep = this.Find(j);

	// Elements are in same set, no need to
	// unite anything.
	if (irep == jrep)
		return;
	
	// Get the rank of i’s tree
	irank = Rank[irep],

	// Get the rank of j’s tree
	jrank = Rank[jrep];

	// If i’s rank is less than j’s rank
	if (irank < jrank) {

		// Then move i under j
		this.parent[irep] = jrep;
	}

	// Else if j’s rank is less than i’s rank
	else if (jrank < irank) {

		// Then move j under i
		this.Parent[jrep] = irep;
	}

	// Else if their ranks are the same
	else {

		// Then move i under j (doesn’t matter
		// which one goes where)
		this.Parent[irep] = jrep;

		// And increment the result tree’s
		// rank by 1
		Rank[jrep]++;
	}
}

// C++ implementation of disjoint set

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

class DisjSet {
	int *rank, *parent, n;

public:

	// Constructor to create and
	// initialize sets of n items
	DisjSet(int n)
	{
		rank = new int[n];
		parent = new int[n];
		this->n = n;
		makeSet();
	}

	// Creates n single item sets
	void makeSet()
	{
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}

	// Finds set of given item x
	int find(int x)
	{
		// Finds the representative of the set
		// that x is an element of
		if (parent[x] != x) {

			// if x is not the parent of itself
			// Then x is not the representative of
			// his set,
			parent[x] = find(parent[x]);

			// so we recursively call Find on its parent
			// and move i's node directly under the
			// representative of this set
		}

		return parent[x];
	}

	// Do union of two sets represented
	// by x and y.
	void Union(int x, int y)
	{
		// Find current sets of x and y
		int xset = find(x);
		int yset = find(y);

		// If they are already in same set
		if (xset == yset)
			return;

		// Put smaller ranked item under
		// bigger ranked item if ranks are
		// different
		if (rank[xset] < rank[yset]) {
			parent[xset] = yset;
		}
		else if (rank[xset] > rank[yset]) {
			parent[yset] = xset;
		}

		// If ranks are same, then increment
		// rank.
		else {
			parent[yset] = xset;
			rank[xset] = rank[xset] + 1;
		}
	}
};

// Driver Code
int main()
{

	// Function Call
	DisjSet obj(5);
	obj.Union(0, 2);
	obj.Union(4, 2);
	obj.Union(3, 1);

	if (obj.find(4) == obj.find(0))
		cout << "Yes\n";
	else
		cout << "No\n";
	if (obj.find(1) == obj.find(0))
		cout << "Yes\n";
	else
		cout << "No\n";

	return 0;
}