Number of Provinces

class Solution {
    vector<int> par;
    int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
public:
    int findCircleNum(vector<vector<int>>& g) {
        int n = g.size();
        par.resize(n);
        iota(par.begin(), par.end(), 0);
        int comps = n;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (g[i][j]) {
                    int a = find(i), b = find(j);
                    if (a != b) { par[a] = b; --comps; }
                }
        return comps;
    }
};

func findCircleNum(g [][]int) int {
    n := len(g)
    par := make([]int, n)
    for i := range par {
        par[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if par[x] != x {
            par[x] = find(par[x])
        }
        return par[x]
    }
    comps := n
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if g[i][j] == 1 {
                a, b := find(i), find(j)
                if a != b {
                    par[a] = b
                    comps--
                }
            }
        }
    }
    return comps
}

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        par = list(range(n))

        def find(x: int) -> int:
            while par[x] != x:
                par[x] = par[par[x]]
                x = par[x]
            return x

        comps = n
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    a, b = find(i), find(j)
                    if a != b:
                        par[a] = b
                        comps -= 1
        return comps

function findCircleNum(isConnected) {
    const n = isConnected.length;
    const par = Array.from({ length: n }, (_, i) => i);
    const find = (x) => {
        while (par[x] !== x) {
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    };
    let comps = n;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j]) {
                const a = find(i), b = find(j);
                if (a !== b) {
                    par[a] = b;
                    comps--;
                }
            }
        }
    }
    return comps;
}

class Solution {
    private int[] par;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        par = new int[n];
        for (int i = 0; i < n; i++) par[i] = i;
        int comps = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    int a = find(i), b = find(j);
                    if (a != b) {
                        par[a] = b;
                        comps--;
                    }
                }
            }
        }
        return comps;
    }

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

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const par: number[] = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => {
        while (par[x] !== x) {
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    };
    let comps = n;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j]) {
                const a = find(i), b = find(j);
                if (a !== b) {
                    par[a] = b;
                    comps--;
                }
            }
        }
    }
    return comps;
}