[leetcode] 547. Number of provinces (medium)

One 、 subject

1、 Title Description

Yes n Cities , Some of them are connected to each other , Others are not connected . If the city a And the city b Direct connection , And the city b And the city c Direct connection , So the city a And the city c Indirectly connected .

Province It's a group of directly or indirectly connected cities , There are no other cities in the group that are not connected .

To give you one n x n Matrix isConnected , among isConnected[i][j] = 1 It means the first one i Two cities and j The two cities are directly connected , and isConnected[i][j] = 0 The two are not directly connected .

Back in the matrix Province The number of .

Example 1：

 Input ：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
 Output ：2

Example 2：

 Input ：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
 Output ：3

2、 Basic framework

3、 Original link

547. Number of provinces

Two 、 Problem solving report

1、 Thought analysis

   Use the union search set to put the connected islands into the same set , Finally, you only need to determine the number of sets

2、 Time complexity

3、 Code details

C++ edition

Writing a ： It makes full use of rank merging and path compression of the union search set

class Solution {
    
public:
    class UnionFind {
    
    public:
        vector<int> parents; // Record the father of each element 
        vector<int> size; // Record the number of elements representing the set of elements 
        vector<int> help; // Auxiliary array , Used for path compression 
        int sets; // The number of sets 

        UnionFind(int n) {
    
            parents.resize(n);
            size.resize(n);
            help.resize(n);
            sets = n;
            for (int i = 0; i < n; i++) {
    
                parents[i] = i;
                size[i] = 1;
            }
        }

        int find(int i) {
    
            int hi = 0;
            while (i != parents[i]) {
    
                help[hi++] = i;
                i = parents[i];
            }

            for (hi--; hi >= 0; hi--) {
     // Path compression 
                parents[help[hi]] = i;
            }

            return i;
        }

        void  myUnion(int i, int j) {
    
            int fi = find(i), fj = find(j);
            if (fi != fj) {
     // Rank consolidation , Hang the representative node with fewer elements in the set to the representative node with more elements in the set 
                if (size[fi] >= size[fj]) {
    
                    parents[fj] = fi;
                    size[fi] += size[fj]; 
                } else {
    
                    parents[fi] = fj;
                    size[fj] += size[fi];
                }
                sets--;
            }
        }

        int setSize() {
    
            return sets;
        }

    };

    int findCircleNum(vector<vector<int>>& isConnected) {
    
        UnionFind *uf = new UnionFind(isConnected.size());
        for (int i = 0; i < isConnected.size(); i++) {
    
            for (int j = i + 1; j < isConnected.size(); j++) {
    
                if (isConnected[i][j] == 1) {
    
                    uf->myUnion(i, j);
                }
            }
        }
        return uf->setSize();
    }
};

Write two ： Only the path compression of joint search set is used , Rank merging is not used

class Solution {
    
public:
    int find(vector<int> &parents, int i) {
    
        return parents[i] == i ? i : parents[i] = find(parents, parents[i]);
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
    
        int n = isConnected.size();

        int ans = n;
        vector<int> parents(n);

        for (int i = 0; i < n; i++) {
    
            parents[i] = i; // initialization , Each element is in a separate set 
        }

        for (int i = 0; i < n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    
                if (isConnected[i][j] == 1) {
    
                    int fi = find(parents, i), fj = find(parents, j);
                    if (fi != fj) {
     // Not merged by rank 
                        parents[fi] = fj;
                        ans--;
                    }
                }
            }
        }

        return ans;
    }
};

Java edition

//  The title is leetcode The original title is 
//  Test link ：https://leetcode.com/problems/friend-circles/
public class FriendCircles {
    

	public static int findCircleNum(int[][] M) {
    
		int N = M.length;
		// {0} {1} {2} {N-1}
		UnionFind unionFind = new UnionFind(N);
		for (int i = 0; i < N; i++) {
    
			for (int j = i + 1; j < N; j++) {
    
				if (M[i][j] == 1) {
     // i and j Know each other 
					unionFind.union(i, j);
				}
			}
		}
		return unionFind.sets();
	}

	public static class UnionFind {
    
		// parent[i] = k ： i His father is k
		private int[] parent;
		// size[i] = k ：  If i Represents the node ,size[i] It makes sense , Otherwise, it doesn't make sense 
		// i What is the size of the collection 
		private int[] size;
		//  Auxiliary structure 
		private int[] help;
		//  How many collections are there 
		private int sets;

		public UnionFind(int N) {
    
			parent = new int[N];
			size = new int[N];
			help = new int[N];
			sets = N;
			for (int i = 0; i < N; i++) {
    
				parent[i] = i;
				size[i] = 1;
			}
		}

		//  from i Start all the way up , Up to no more up , Represents a node , return 
		//  This process requires path compression 
		private int find(int i) {
    
			int hi = 0;
			while (i != parent[i]) {
    
				help[hi++] = i;
				i = parent[i];
			}
			for (hi--; hi >= 0; hi--) {
    
				parent[help[hi]] = i;
			}
			return i;
		}

		public void union(int i, int j) {
    
			int f1 = find(i);
			int f2 = find(j);
			if (f1 != f2) {
    
				if (size[f1] >= size[f2]) {
    
					size[f1] += size[f2];
					parent[f2] = f1;
				} else {
    
					size[f2] += size[f1];
					parent[f1] = f2;
				}
				sets--;
			}
		}

		public int sets() {
    
			return sets;
		}
	}
}