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