leetcode

Solution to some Leetcode problems written in C++

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

2092.cpp (1772B)

0 int n, cnt = n; 1 mutable vector<int> root; 2 vector<int> size; 3 4 public: 5 UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); } 6 UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {} 7 8 int find(int x) const { 9 while (x != root[x]) 10 x = root[x] = root[root[x]]; 11 return x; 12 } 13 14 void join(int x, int y) { 15 x = find(x), y = find(y); 16 if (x != y) { 17 if (size[x] > size[y]) swap(x, y); 18 root[x] = y; 19 size[y] += size[x]; 20 cnt--; 21 } 22 } 23 24 void reset(int x) { 25 root[x] = x; 26 size[x] = 0; 27 } 28 29 int count() const { return cnt; } 30 bool connected(int x, int y) const { return find(x) == find(y); } 31 } 32 ; 33 34 class Solution { 35 public: 36 vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson) { 37 sort(begin(meetings), end(meetings), [](const auto &m1, const auto &m2) { return m1[2] < m2[2]; }); 38 39 int first = 0; 40 UnionFind uf(n); 41 uf.join(0, firstPerson); 42 43 meetings.push_back({0, 0, INT_MAX}); 44 uf.join(meetings[0][0], meetings[0][1]); 45 for (int i = 1; i < size(meetings); i++) { 46 if (meetings[i][2] == meetings[i - 1][2]) { 47 uf.join(meetings[i][0], meetings[i][1]); 48 } else { 49 for (int j = first; j < i; j++) { 50 if (uf.connected(meetings[j][0], 0)) continue; 51 uf.reset(meetings[j][0]); 52 uf.reset(meetings[j][1]); 53 } 54 first = i; 55 uf.join(meetings[i][0], meetings[i][1]); 56 } 57 } 58 59 vector<int> res; 60 for (int i = 0; i < n; i++) { 61 if (uf.connected(i, 0)) res.push_back(i); 62 } 63 return res; 64 } 65 };