leetcode

0 class UnionFind {

1 int n, cnt = n;

2 vector<int> root, size;

3

4 public:

5 UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); }

6

7 UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}

8

9 static int redundant;

10

11 int find(int x) {

12 while (x != root[x])

13 x = root[x] = root[root[x]];

14 return x;

15 }

16

17 void join(int x, int y) {

18 x = find(x), y = find(y);

19 if (x != y) {

20 if (size[x] > size[y]) swap(x, y);

21 root[x] = y;

22 size[y] += size[x];

23 cnt--;

24 } else

25 redundant++;

26 }

27

28 int count() { return cnt; }

29 bool connected(int x, int y) { return find(x) == find(y); }

30 };

31

32 int UnionFind::redundant = 0;

33

34 class Solution {

35 public:

36 int maxNumEdgesToRemove(int n, vector<vector<int>> &e) {

37 UnionFind::redundant = 0;

38

39 UnionFind a(n + 1);

40 for (int i = 0; i < e.size(); i++)

41 if (e[i][0] == 3) a.join(e[i][1], e[i][2]);

42

43 UnionFind b = a;

44 for (int i = 0; i < e.size(); i++)

45 if (e[i][0] == 1)

46 a.join(e[i][1], e[i][2]);

47 else if (e[i][0] == 2)

48 b.join(e[i][1], e[i][2]);

49

50 // count must be 2, since 0 is not used

51 return a.count() == 2 && b.count() == 2 ? UnionFind::redundant : -1;

52 }

53 };