14. Check the implementation and features of the set
Check and Set (Dijoint Set) is a data structure by leaps and bounds, that is to say that you won’t be that you are not at all, if you will use to go for a while, it not too much to let you in the development of space, or the need to like dynamic programming or various search has a very strong random strain and above for the space of free play. So we are mainly its situation and its implementation code to learn to master. Master the code template directly on the use.
Dijoint Set
Applicable scenario
It solve the problems of the scene is the organizer and matching, that is to say, in some realistic problems, you need to quickly figure out whether the two individuals in a collection, so speak a bit abstract, most of the time that is to say you and his friend is such a problem, if it is in a social network, and judge between the two groups, Is not a group and merges groups very quickly, so you need to use data structures like this.
- Group and pairing problems
- Group or not?
Suppose you have to implement the functions of friends and so-called circle of friends on wechat yourself, and analyze whether these two people are friends or not, think about how you should implement it?
Let’s say we have n people, from zero to n-1, so that you can very quickly determine whether a and B are friends or not, and that you can support some operations, like turning A into B’s friend. Things like that, if you’re doing it, you might think of things like a set or a dictionary for people who are friends, and then you might find that you have a problem, that you might have a lot of sets, like two of them are friends, but they’re not friends, And at the back of you want to merge the set and so on, the operation and it’s hard to tell that a bunch of friends a group it is belong to which a group of issues such as such as, so for this reason, was invented to a data structure, the data structure is called “and check”, dedicated to solve such problems.
Basic operation
To solve this scenario, there are three main functions to implement:
- MakeSet (s) : Creates a new lookup set with s single-element sets.
- UnionSet (X, Y) : Merges the set where element X and element Y are located, requiring that the sets where element X and y are located do not intersect. If they do, the merges will not occur.
- Find (x) : Finds the representation of the set in which element x is located. This operation can also be used to determine whether two elements are in the same set by comparing their representatives.
And look up the set principle
Initialize the
To learn from the set principle, each element starts off with a parent array pointing to itself, and each element has a parent array pointing to itself which means that it’s its own collection or its own boss,
Query, merge
Next is an operation called merge and query:
- How to query any element, look at its parent and then look at its parent and then go up until its parent is equal to itself, which means find its leading element, which is its set and that means who that set is.
- How to merge, let’s say we want to merge these two sets, one of the things we do is find the leader of the set, in this case A, and another set whose leader is E, and then either point parent[e] to A or parent[a] to E, both of which are the same operation, The last word is the so-called merger of the two.
Path to the compression
There is also something called path compression, and here we see:
- D’s parent is C
- The parent of C is B
- B’s parent is A so we can just put all the elements along this path, its parent points to A. This will be the same as the original table, but the query time will be much faster.
And look up the set code template
Java
// Java
class UnionFind {
private int count = 0;
private int[] parent;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while(p ! = parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
}
Copy the codePython
# Python
def init(p):
# for i = 0 .. n: p[i] = i;
p = [i for i in range(n)]
def union(self, p, i, j):
p1 = self.parent(p, i)
p2 = self.parent(p, j)
p[p1] = p2
def parent(self, p, i):
root = i
whilep[root] ! = root:
root = p[root]
whilep[i] ! = i:Path compression?
x = i; i = p[i]; p[x] = root
return root
Copy the codeC/C++
//C/C++
class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent.push_back(i * n + j);
++count;
}
else {
parent.push_back(-1);
}
rank.push_back(0);
}
}
}
/ / recursion
int find(int i) {
if(parent[i] ! = i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if(rootx ! = rooty) {
if (rank[rootx] < rank[rooty]) {
swap(rootx, rooty);
}
parent[rooty] = rootx;
if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
--count;
}
}
int getCount() const {
return count;
}
private:
vector<int> parent;
vector<int> rank;
int count;
};
Copy the codeJavaScript
// JavaScript
class unionFind {
constructor(n) {
this.count = n;
this.parent = new Array(n);
for (let i = 0; i < n; i++) {
this.parent[i] = i;
}
}
find(p) {
let root = p;
while(parent[root] ! == root) {
root = parent[root];
}
// Compression path
while(parent[p] ! == p) {
let x = p;
p = this.parent[p];
this.parent[x] = root;
}
return root;
}
union(p, q) {
let rootP = find(p);
let rootQ = find(q);
if (rootP === rootQ) return;
this.parent[rootP] = rootQ;
this.count--;
}
}
Copy the codePractical subject
547. A circle of friends
200. Number of islands
130. The surrounding area
Here is only the circle of friends of this problem to explain, the other can go to practice.
547. A circle of friends
Method 1: DFS, BFS (Island like problem)
class Solution {
// 1. DFS,BFS (similar to island problem)
// Time (n^2) space (n)
public int findCircleNum(int[][] M) {
/ * *
* Use a Visited array to judge each node in turn
* If it is not visited, the circle of friends is increased by 1 and a DFS search is performed on the node to mark all visited nodes.
* /
boolean[] visited = new boolean[M.length];
int res = 0;
// Walk through all the students
for (int i = 0; i < M.length; i++) {
// when the student has not been accessed, res++ is used
if(! visited[i]) {
// Meanwhile the DFS student and all his friends (similar to the island problem)
dfs(M, visited, i);
res++;
}
}
return res;
}
private void dfs(int[][] M, boolean[] visited, int i) {
// DFS has no Terminator at first
// This is also a special case, because its Terminator is that everything is accessed, no need to spread
// For all currently accessed nodes I, then iterate over the other nodes, i.e. student 0 repeats 0 through m. length
for (int j = 0; j < M.length; j++) {
// if M[I][j] = 1, it means that I and j are friends and j has not been accessed
if(M[i][j] == 1 && ! visited[j]) {
visited[j] = true;
dfs(M, visited, j);
}
}
}
}
Copy the codeMethod 2: Query the set
class Solution {
O(n^3) O(n^3)
public int findCircleNum(int[][] M) {
if (M == null || M.length == 0) return 0;
int n = M.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n - 1; i ++) {
for (int j = i + 1; j < n; j++) {
if (M[i][j] == 1) uf.union(i, j);
}
}
return uf.count;
}
class UnionFind {
public int count = 0;
public int[] parent;
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int p) {
while(p ! = parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union (int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
}
}
Copy the code
Some pictures from the network, copyright to the original author, delete.Copy the code