261. Graph valid tree

#include <stdbool.h>
#include <stdlib.h>

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

bool validTree(int n, int **edges, int edgesSize, int *edgesColSize) {
  (void)edgesColSize; // always 2
  int count = n;
  int *parent = calloc(n + 1, sizeof(int));
  for (int i = 1; i <= n; i++)
    parent[i] = i;

  bool ok = true;
  for (int i = 0; i < edgesSize; i++) {
    int ra = find(parent, edges[i][0]);
    int rb = find(parent, edges[i][1]);
    if (ra == rb) {
      ok = false; // cycle
      break;
    }
    count--;
    parent[rb] = ra;
  }

  free(parent);
  return ok && count == 1;
}

#include <vector>

using namespace std;

class Solution {
public:
  bool validTree(int n, vector<vector<int>> &edges) {
    int count = n;
    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 false;
      else
        count--;
      parent[rb] = ra;
    }
    return count == 1;
  }

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

package graphs

func validTree(n int, edges [][]int) bool {
    count := n
    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 false
        }
        count--
        parent[rb] = ra
    }
    return count == 1
}

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

class Solution {
    public boolean validTree(int n, int[][] edges) {
        int count = n;
        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 false;
            else
                count--;
            parent[rb] = ra;
        }
        return count == 1;
    }

    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} n
 * @param {number[][]} edges
 * @return {boolean}
 */
var validTree = function (n, edges) {
  let count = n;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);

  for (const [a, b] of edges) {
    const ra = find(parent, a);
    const rb = find(parent, b);
    if (ra === rb) return false;
    count--;
    parent[rb] = ra;
  }
  return count === 1;
};

from typing import List


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

        for a, b in edges:
            ra = self.find(parent, a)
            rb = self.find(parent, b)
            if ra == rb:
                return False
            count -= 1
            parent[rb] = ra
        return count == 1

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

impl Solution {
    pub fn valid_tree(n: i32, edges: Vec<Vec<i32>>) -> bool {
        let mut count = n;
        let mut parent: Vec<usize> = (0..=n as usize).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 false;
            }
            count -= 1;
            parent[rb] = ra;
        }
        count == 1
    }

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