leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0547.cpp (938B)

0 class UnionFind { 1 vector<int> root, rank; 2 int n; 3 4 public: 5 UnionFind(int n) : n(n), root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); } 6 7 int find(int x) { 8 while (x != root[x]) 9 x = root[x] = root[root[x]]; 10 return x; 11 } 12 13 void join(int x, int y) { 14 x = find(x), y = find(y); 15 16 if (x != y) { 17 if (rank[x] > rank[y]) swap(x, y); 18 19 root[x] = y; 20 rank[y] += rank[x]; 21 } 22 } 23 24 int count() { 25 int cnt = 0; 26 for (int i = 0; i < n; i++) 27 cnt += root[i] == i; 28 return cnt; 29 } 30 }; 31 32 class Solution { 33 public: 34 int findCircleNum(vector<vector<int>> &isConnected) { 35 int n = isConnected.size(); 36 UnionFind uf(n); 37 for (int i = 0; i < n; i++) 38 for (int j = i + 1; j < n; j++) 39 if (isConnected[i][j]) uf.join(i, j); 40 41 return uf.count(); 42 } 43 };