Skip to content

1579. Remove Max Number of Edges to Keep Graph Fully Traversable 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class UnionFind {
 public:
  UnionFind(int n) : count(n), id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  bool unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return false;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
    --count;
    return true;
  }

  int getCount() const {
    return count;
  }

 private:
  int count;
  vector<int> id;
  vector<int> rank;

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }
};

class Solution {
 public:
  int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
    UnionFind alice(n);
    UnionFind bob(n);
    int requiredEdges = 0;

    // Greedily put type 3 edges in the front.
    ranges::sort(edges, ranges::greater{},
                 [](const vector<int>& edge) { return edge[0]; });

    for (const vector<int>& edge : edges) {
      const int type = edge[0];
      const int u = edge[1] - 1;
      const int v = edge[2] - 1;
      switch (type) {
        case 3:  // Can be traversed by Alice and Bob.
          // Note that we should use | instead of || because if the first
          // expression is true, short-circuiting will skip the second
          // expression.
          if (alice.unionByRank(u, v) | bob.unionByRank(u, v))
            ++requiredEdges;
          break;
        case 2:  // Can be traversed by Bob.
          if (bob.unionByRank(u, v))
            ++requiredEdges;
          break;
        case 1:  // Can be traversed by Alice.
          if (alice.unionByRank(u, v))
            ++requiredEdges;
          break;
      }
    }

    return alice.getCount() == 1 && bob.getCount() == 1
               ? edges.size() - requiredEdges
               : -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class UnionFind {
  public UnionFind(int n) {
    count = n;
    id = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; ++i)
      id[i] = i;
  }

  public boolean unionByRank(int u, int v) {
    final int i = find(u);
    final int j = find(v);
    if (i == j)
      return false;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
    --count;
    return true;
  }

  public int getCount() {
    return count;
  }

  private int count;
  private int[] id;
  private int[] rank;

  private int find(int u) {
    return id[u] == u ? u : (id[u] = find(id[u]));
  }
}

class Solution {
  public int maxNumEdgesToRemove(int n, int[][] edges) {
    UnionFind alice = new UnionFind(n);
    UnionFind bob = new UnionFind(n);
    int requiredEdges = 0;

    // Greedily put type 3 edges in the front.
    Arrays.sort(edges, (a, b) -> Integer.compare(b[0], a[0]));

    for (int[] edge : edges) {
      final int type = edge[0];
      final int u = edge[1] - 1;
      final int v = edge[2] - 1;
      switch (type) {
        case 3: // Can be traversed by Alice and Bob.
          // Note that we should use | instead of || because if the first
          // expression is true, short-circuiting will skip the second
          // expression.
          if (alice.unionByRank(u, v) | bob.unionByRank(u, v))
            ++requiredEdges;
          break;
        case 2: // Can be traversed by Bob.
          if (bob.unionByRank(u, v))
            ++requiredEdges;
          break;
        case 1: // Can be traversed by Alice.
          if (alice.unionByRank(u, v))
            ++requiredEdges;
      }
    }

    return alice.getCount() == 1 && bob.getCount() == 1 ? edges.length - requiredEdges : -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class UnionFind:
  def __init__(self, n: int):
    self.count = n
    self.id = list(range(n))
    self.rank = [0] * n

  def unionByRank(self, u: int, v: int) -> bool:
    i = self._find(u)
    j = self._find(v)
    if i == j:
      return False
    if self.rank[i] < self.rank[j]:
      self.id[i] = j
    elif self.rank[i] > self.rank[j]:
      self.id[j] = i
    else:
      self.id[i] = j
      self.rank[j] += 1
    self.count -= 1
    return True

  def _find(self, u: int) -> int:
    if self.id[u] != u:
      self.id[u] = self._find(self.id[u])
    return self.id[u]


class Solution:
  def maxNumEdgesToRemove(self, n: int, edges: list[list[int]]) -> int:
    alice = UnionFind(n)
    bob = UnionFind(n)
    requiredEdges = 0

    # Greedily put type 3 edges in the front.
    for type_, u, v in sorted(edges, reverse=True):
      u -= 1
      v -= 1
      if type_ == 3:  # Can be traversed by Alice and Bob.
          # Note that we should use | instead of or because if the first
          # expression is True, short-circuiting will skip the second
          # expression.
        if alice.unionByRank(u, v) | bob.unionByRank(u, v):
          requiredEdges += 1
      elif type_ == 2:  # Can be traversed by Bob.
        if bob.unionByRank(u, v):
          requiredEdges += 1
      else:  # type == 1 Can be traversed by Alice.
        if alice.unionByRank(u, v):
          requiredEdges += 1

    return (len(edges) - requiredEdges
            if alice.count == 1 and bob.count == 1
            else -1)