無向グラフにおける連結成分の数え上げ

この問題では、与えられた無向グラフに含まれる連結成分の総数を求める必要があります。Union-Find（素集合データ構造）を用いることで効率的に解決できます。各ノードを初期状態で自身を親とする木として扱い、エッジを通じてノードを結合していきます。パス圧縮により探索効率を高め、最終的なルートノードの数が答えとなります。

class Solution {
    public int countComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] e : edges) {
            uf.connect(e[0], e[1]);
        }
        return uf.getGroupCount();
    }

    static class UnionFind {
        private int[] root;
        private int groups;

        UnionFind(int size) {
            root = new int[size];
            for (int i = 0; i < size; i++) {
                root[i] = i;
            }
            groups = size;
        }

        int findRoot(int x) {
            if (root[x] != x) {
                root[x] = findRoot(root[x]); // パス圧縮
            }
            return root[x];
        }

        void connect(int x, int y) {
            int rx = findRoot(x);
            int ry = findRoot(y);
            if (rx != ry) {
                root[rx] = ry;
                groups--;
            }
        }

        int getGroupCount() {
            return groups;
        }
    }
}

境界に接していない領域の変換

盤面上で、境界に接していない'O'を'X'に変更する問題です。境界から到達可能な'O'を一時的に別の文字に置き換え、その後、残った'O'を'X'に、置き換えた文字を元に戻すという手法を取ります。深さ優先探索（DFS）を使って境界から到達可能な領域を特定します。

class Solution {
    public void solve(char[][] board) {
        if (board.length == 0) return;
        int rows = board.length, cols = board[0].length;

        // 境界の'O'からDFS開始
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O') markSafe(board, i, 0);
            if (board[i][cols - 1] == 'O') markSafe(board, i, cols - 1);
        }
        for (int j = 0; j < cols; j++) {
            if (board[0][j] == 'O') markSafe(board, 0, j);
            if (board[rows - 1][j] == 'O') markSafe(board, rows - 1, j);
        }

        // 盤面の更新
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    private void markSafe(char[][] b, int x, int y) {
        if (x < 0 || x >= b.length || y < 0 || y >= b[0].length || b[x][y] != 'O') return;
        b[x][y] = '#';
        markSafe(b, x + 1, y);
        markSafe(b, x - 1, y);
        markSafe(b, x, y + 1);
        markSafe(b, x, y - 1);
    }
}

等式制約の充足可能性判定

複数の等式と不等式で表される変数間の関係について、すべての条件を同時に満たす割り当てが存在するかを判定します。まず等式に基づいて変数同士をUnion-Findで結合し、次に各不等式に対して両辺の変数が同じグループに属していないことを確認します。

class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26); // 小文字アルファベット26文字
        // 等式を処理
        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int var1 = eq.charAt(0) - 'a';
                int var2 = eq.charAt(3) - 'a';
                uf.connect(var1, var2);
            }
        }
        // 不等式を検証
        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int var1 = eq.charAt(0) - 'a';
                int var2 = eq.charAt(3) - 'a';
                if (uf.findRoot(var1) == uf.findRoot(var2)) {
                    return false;
                }
            }
        }
        return true;
    }

    static class UnionFind {
        private int[] parent;

        UnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        int findRoot(int x) {
            if (parent[x] != x) {
                parent[x] = findRoot(parent[x]);
            }
            return parent[x];
        }

        void connect(int x, int y) {
            int rootX = findRoot(x);
            int rootY = findRoot(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
    }
}