Ruby - Union Find Kruskal's Algorithm with comments
Rephrase task\n\nAssume we do not have any edges initially: only some set of vertices (numbers from 1 to n). And some set of edges that we can use to make graph
## Rephrase task\n\nAssume we do not have any edges initially: only some set of vertices (numbers from 1 to n). And some set of edges that we can use to make graph traversable by both Alice and Bob. Number of edges in the set minus minimum number of edges to add (to make graph traversable by both Alice and Bob) equals to the initial value we need to calculate.\n\n## Observation\n\nEdges that are traversable by both Alice and Bob should be preoritasable over others edges. But only if any new age does not add a cycle in the graph. At the end we should have `n - 1` edges traversable by Alice and `n - 1` edges traversable by Bob. Some of them may be shared (if can by traversed by both Alice and Bob). So we need from `n - 1`  upto ` 2(n - 1)` edges to make graph traversable by both.\n\n## Algorithm\n\nSplit edges by three groups (like in task description). Use `merge` method from Union Find algorithm to to check whether we can add next edge not adding cycles (vertices `u` and `v` should be in different groups). First use up to `n - 1` edges traversed by both Alice and Bob, then use up to `n - 1` edges traversed by Alice, and then use up to `n - 1` edges traversed by Bob. Return number not used edges if we have enough edges for Alice and Bob or `-1` if we ran out of edges.\n\n## Implementation\n\nRuby version\n\n```ruby\n# find with path compression\ndef find(par, x)\n  par[x] == x ? x : (par[x] = find(par, par[x]))\nend\n\ndef merge(par, x, y)\n  x = find(par, x)\n  y = find(par, y)\n  return false if x == y\n  par[x] = y\n  return true\nend\n\nALICE = 1\nBOB = 2\nBOTH = 3\n\ndef max_num_edges_to_remove(n, edges)\n  res = edges.size # all minus min needed num of edges to make graph traversable\n                   # (remaining count after adding all nessasary edges)\n  return res if n == 1\n  return -1 if edges.size < n - 1 # not enough edges to make graph traversable\n\n  edges_for = edges.group_by(&:first)\n  return -1 if edges_for.keys.one? && edges_for.keys[0] != BOTH # not enough edges for Alice or Bob\n  \n  # Initially, each vertice is in its own single-vertice group where the vertice is the parent of that group.\n  par_alice = *0..n\n  need_alice = n - 1\n  \n  edges_for[BOTH]&.each do |_, u, v|\n    if merge(par_alice, u, v)\n      res -= 1\n      need_alice -= 1\n      return res if need_alice == 0\n    end\n  end\n  \n  par_bob = par_alice.dup\n  need_bob = need_alice\n  \n  edges_for[ALICE]&.each do |_, u, v|\n    if merge(par_alice, u, v)\n      res -= 1\n      need_alice -= 1\n      break if need_alice == 0\n    end\n  end\n  return -1 if need_alice > 0\n  \n  edges_for[BOB]&.each do |_, u, v|\n    if merge(par_bob, u, v)\n      res -= 1\n      need_bob -= 1\n      return res if need_bob == 0\n    end\n  end\n  \n  return -1\nend\n# Runtime: 216 ms\n```\n\n## Videos for Union Find (by William Fiset):\n- [Union Find Introduction](https://www.youtube.com/watch?v=ibjEGG7ylHk)\n- [Union Find Kruskal\'s Algorithm](https://www.youtube.com/watch?v=JZBQLXgSGfs)\n- [Union Find - Union and Find Operations](https://www.youtube.com/watch?v=0jNmHPfA_yE)\n- [Union Find Path Compression](https://www.youtube.com/watch?v=VHRhJWacxis)\n- [Union Find Code](https://www.youtube.com/watch?v=KbFlZYCpONw)\n\n[LeetCode Union Find Problems](https://leetcode.com/tag/union-find/)\n
['Union Find', 'Ruby']