LeetCode Problem: Union Find Topics

algorithm

LeetCode Problem: Union Find Topics

1. Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v. Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3


Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3

To solve this problem, we need to use a data structure called Disjoint Set Union(DSU), which has two options union and find. Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class RedundantConnection {
    public int[] findRedundantConnection(int[][] edges) {
        int len = edges.length;
        DSU dsu = new DSU(len + 1);
        for (int[] edge : edges) {
            if (!dsu.union(edge[0], edge[1])) {
                return edge;
            }
        }
        return null;
    }
    
    // We use a inner class DSU to implement disjoint set union.
    class DSU {
        private int[] parents;
        private int[] rank;// rank is the number of children

        DSU(int n) {
            parents = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++)
                parents[i] = i;
        }

        boolean union(int a, int b) {// union by rank
            int p1 = find(a);
            int p2 = find(b);

            if (p1 == p2) return false;

            if (rank[p1] >= rank[p2]) {
                rank[p1]++;
                parents[p2] = p1;
            } else {
                rank[p2]++;
                parents[p1] = p2;
            }
            return true;
        }

        private int find(int a) {
            // Each time we find a node, we do the path compression.
            if (parents[a] != a){
                parents[a] = find(parents[a]);
            }
            return parents[a];
        }
    }
}

The process of the above code is like this:

2. Friend Circles

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:
Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.


Example 2:
Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Here is the code to solve this problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.HashSet;
import java.util.Set;

public class FriendCircles {
    public int findCircleNum(int[][] M) {
        int len = M.length;
        DSU dsu = new DSU(len);

        // We traverse the matrix and union all direct friends.
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (M[i][j] == 1) {
                    dsu.union(i, j);
                }
            }
        }

        // We count the number of parents, which is also
        // the number of circles.
        Set<Integer> circles = new HashSet<>();
        for (int i = 0; i < len; i++) {
            circles.add(dsu.find(i));
        }

        return circles.size();
    }

    // We use a inner class DSU to implement disjoint set union.
    class DSU {
        private int[] parents;
        private int[] rank;// rank is the number of children

        DSU(int n) {
            parents = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++)
                parents[i] = i;
        }

        boolean union(int a, int b) {// union by rank
            int p1 = find(a);
            int p2 = find(b);

            if (p1 == p2) return false;

            if (rank[p1] >= rank[p2]) {
                rank[p1]++;
                parents[p2] = p1;
            } else {
                rank[p2]++;
                parents[p1] = p2;
            }
            return true;
        }

        private int find(int a) {
            // Each time we find a node, we do the path compression.
            if (parents[a] != a) {
                parents[a] = find(parents[a]);
            }
            return parents[a];
        }
    }
}