684. Redundant connection

#include <stdlib.h>

static int find(const int *parent, int x) {
  while (parent[x] != x)
    x = parent[x];
  return x;
}

int *findRedundantConnection(int **edges, int edgesSize, int *edgesColSize,
                             int *returnSize) {
  (void)edgesColSize; // always 2
  int n = edgesSize;
  int *parent = malloc((n + 1) * sizeof(int));
  for (int i = 1; i <= n; i++)
    parent[i] = i;

  int *result = malloc(2 * sizeof(int));
  *returnSize = 0;
  for (int i = 0; i < edgesSize; i++) {
    int ra = find(parent, edges[i][0]);
    int rb = find(parent, edges[i][1]);
    if (ra == rb) {
      result[0] = edges[i][0], result[1] = edges[i][1];
      *returnSize = 2;
      break;
    }
    parent[rb] = ra;
  }

  free(parent);
  return result;
}

#include <vector>

using namespace std;

class Solution {
public:
  vector<int> findRedundantConnection(vector<vector<int>> &edges) {
    int n = edges.size();
    vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++)
      parent[i] = i;

    for (auto &edge : edges) {
      int ra = find(parent, edge[0]);
      int rb = find(parent, edge[1]);
      if (ra == rb)
        return edge;
      parent[rb] = ra;
    }
    return {};
  }

private:
  int find(vector<int> &parent, int x) {
    while (parent[x] != x)
      x = parent[x];
    return x;
  }
};

package graphs

func findRedundantConnection(edges [][]int) []int {
    n := len(edges)
    parent := make([]int, n+1)
    for i := 1; i <= n; i++ {
        parent[i] = i
    }

    for _, edge := range edges {
        ra := find(parent, edge[0])
        rb := find(parent, edge[1])
        if ra == rb {
            return edge
        }
        parent[rb] = ra
    }
    return []int{}
}

func find(parent []int, x int) int {
    for parent[x] != x {
        x = parent[x]
    }
    return x
}

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; i++)
            parent[i] = i;

        for (int[] edge : edges) {
            int ra = find(parent, edge[0]);
            int rb = find(parent, edge[1]);
            if (ra == rb)
                return edge;
            parent[rb] = ra;
        }
        return new int[0];
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x)
            x = parent[x];
        return x;
    }
}

const find = (parent, x) => {
  while (parent[x] !== x) x = parent[x];
  return x;
};

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);

  for (const edge of edges) {
    const ra = find(parent, edge[0]);
    const rb = find(parent, edge[1]);
    if (ra === rb) return edge;
    parent[rb] = ra;
  }
  return [];
};

from typing import List


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))

        for edge in edges:
            ra = self.find(parent, edge[0])
            rb = self.find(parent, edge[1])
            if ra == rb:
                return edge
            parent[rb] = ra
        return []

    def find(self, parent: List[int], x: int) -> int:
        while parent[x] != x:
            x = parent[x]
        return x

impl Solution {
    pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
        let n = edges.len();
        let mut parent: Vec<usize> = (0..=n).collect();

        for edge in edges {
            let ra = Self::find(&parent, edge[0] as usize);
            let rb = Self::find(&parent, edge[1] as usize);
            if ra == rb {
                return edge;
            }
            parent[rb] = ra;
        }
        Vec::new()
    }

    fn find(parent: &[usize], mut x: usize) -> usize {
        while parent[x] != x {
            x = parent[x];
        }
        x
    }
}