leetcode

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 };