LeetCode Solutions

			

class UnionFind {
 public:
  UnionFind(int n) : id(n) {
    iota(begin(id), end(id), 0);
  }

  bool union_(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return false;
    id[i] = j;
    return true;
  }

 private:
  vector<int> id;

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

class Solution {
 public:
  vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    vector<int> ids(edges.size() + 1);
    int nodeWithTwoParents = 0;

    for (const vector<int>& e : edges) {
      const int v = e[1];
      if (++ids[v] == 2) {
        nodeWithTwoParents = v;
        break;
      }
    }

    // If there is no edge with two ids
    // We don't have to skip any edge
    if (nodeWithTwoParents == 0)
      return findRedundantDirectedConnection(edges, -1);

    for (int i = edges.size() - 1; i >= 0; --i)
      if (edges[i][1] == nodeWithTwoParents)
        // Try to delete edges[i]
        if (findRedundantDirectedConnection(edges, i).empty())
          return edges[i];

    throw;
  }

  vector<int> findRedundantDirectedConnection(const vector<vector<int>>& edges,
                                              int skippedEdgeIndex) {
    UnionFind uf(edges.size() + 1);

    for (int i = 0; i < edges.size(); ++i) {
      if (i == skippedEdgeIndex)
        continue;
      if (!uf.union_(edges[i][0], edges[i][1]))
        return edges[i];
    }

    return {};
  }
};

			

class UnionFind {
  public UnionFind(int n) {
    id = new int[n];
    for (int i = 0; i < n; ++i)
      id[i] = i;
  }

  public boolean union(int u, int v) {
    final int i = find(u);
    final int j = find(v);
    if (i == j)
      return false;
    id[i] = j;
    return true;
  }

  private int[] id;

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

class Solution {
  public int[] findRedundantDirectedConnection(int[][] edges) {
    int[] ids = new int[edges.length + 1];
    int nodeWithTwoParents = 0;

    for (int[] e : edges) {
      final int v = e[1];
      if (++ids[v] == 2) {
        nodeWithTwoParents = v;
        break;
      }
    }

    // If there is no edge with two ids
    // We don't have to skip any edge
    if (nodeWithTwoParents == 0)
      return findRedundantDirectedConnection(edges, -1);

    for (int i = edges.length - 1; i >= 0; --i)
      if (edges[i][1] == nodeWithTwoParents)
        // Try to delete edges[i]
        if (findRedundantDirectedConnection(edges, i).length == 0)
          return edges[i];

    throw new IllegalArgumentException();
  }

  private int[] findRedundantDirectedConnection(int[][] edges, int skippedEdgeIndex) {
    UnionFind uf = new UnionFind(edges.length + 1);

    for (int i = 0; i < edges.length; ++i) {
      if (i == skippedEdgeIndex)
        continue;
      if (!uf.union(edges[i][0], edges[i][1]))
        return edges[i];
    }

    return new int[] {};
  }
}

			

class UnionFind:
  def __init__(self, n: int):
    self.id = [i for i in range(n + 1)]

  def union(self, u: int, v: int) -> bool:
    i = self.find(u)
    j = self.find(v)
    if i == j:
      return False
    self.id[i] = j
    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 findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
    ids = [0] * (len(edges) + 1)
    nodeWithTwoParents = 0

    for u, v in edges:
      ids[v] += 1
      if ids[v] == 2:
        nodeWithTwoParents = v

    def findRedundantDirectedConnection(skippedEdgeIndex: int) -> List[int]:
      uf = UnionFind(len(edges) + 1)

      for i, edge in enumerate(edges):
        if i == skippedEdgeIndex:
          continue
        if not uf.union(edge[0], edge[1]):
          return edge

      return []

    # If there is no edge with two ids
    # We don't have to skip any edge
    if nodeWithTwoParents == 0:
      return findRedundantDirectedConnection(-1)

    for i in reversed(range(len(edges))):
      _, v = edges[i]
      if v == nodeWithTwoParents:
        # Try to delete edges[i]
        if not findRedundantDirectedConnection(i):
          return edges[i]