leetcode

Solution to some Leetcode problems written in C++

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

1319.cpp (1004B)

0 class UnionFind { 1 int n; 2 vector<int> root, rank; 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 if (x != y) { 15 if (rank[x] > rank[y]) swap(x, y); 16 17 root[x] = y; 18 rank[y] += rank[x]; 19 } 20 } 21 22 int count() { 23 int cnt = 0; 24 for (int i = 0; i < n; i++) 25 cnt += root[i] == i; 26 return cnt; 27 } 28 }; 29 30 class Solution { 31 public: 32 int makeConnected(int n, vector<vector<int>> &connections) { 33 int count = 0; 34 UnionFind uf(n); 35 for (auto &edge : connections) { 36 int x = uf.find(edge[0]), y = uf.find(edge[1]); 37 if (x == y) 38 count++; 39 else 40 uf.join(x, y); 41 } 42 return count < uf.count() - 1 ? -1 : uf.count() - 1; 43 } 44 };