323. Connected components

#include <stdlib.h>

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

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

  for (int i = 0; i < edgesSize; i++) {
    int ra = find(parent, edges[i][0]);
    int rb = find(parent, edges[i][1]);
    if (ra != rb)
      count--;
    parent[rb] = ra;
  }

  free(parent);
  return count;
}

#include <vector>

using namespace std;

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

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

package graphs

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

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

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

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

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

from typing import List


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

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

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

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

        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 {
                count -= 1;
            }
            parent[rb] = ra;
        }
        count
    }

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