素集合データ構造 (Union-Find)

素集合データ構造（Disjoint Set Union, DSU）は、要素がどのグループに属するかを管理し、グループの統合と判定を効率的に行うための木構造ベースのデータ構造です。

主要な操作

• find: ある要素がどのグループ（代表元）に属するかを特定する。
• unite: 二つのグループを一つに統合する。

経路圧縮の実装

検索時に再帰的に親を辿り、直接ルートを参照するようにポインタを更新することで、計算量を大幅に削減します。

int findRoot(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = findRoot(parent, parent[x]); // 経路圧縮
    }
    return parent[x];
}

幅優先探索 (BFS)

BFSはグラフやグリッドの探索手法の一つで、開始地点から距離が近い順にノードを訪問します。最短経路を求める際に非常に強力なアルゴリズムです。

void bfs(int start, const vector<vector<int>>& adj) {
    queue<int> q;
    q.push(start);
    vector<bool> visited(n, false);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

最小全域木 (MST)

グラフのすべての頂点を、最小の総コストで接続する部分木を求める問題です。主に「Kruskal法」と「Prim法」が用いられます。

Kruskal法（辺優先）

全ての辺をコスト順に並べ替え、素集合データ構造を用いて閉路ができないように順次辺を選択します。

struct Edge { int u, v, weight; };

bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

// クラスカル法のメインロジック概略
sort(edges.begin(), edges.end(), compareEdges);
for (const auto& edge : edges) {
    if (findRoot(parent, edge.u) != findRoot(parent, edge.v)) {
        unite(parent, edge.u, edge.v);
        totalCost += edge.weight;
    }
}

Prim法（頂点優先）

未訪問の頂点の中から、現在構築中の木に対して最もコストが低い辺で繋がっている頂点を逐次追加していきます。

int prim(int n, const vector<vector<pair<int, int>>>& graph) {
    vector<int> minDist(n, INF);
    vector<bool> inMST(n, false);
    minDist[0] = 0;
    int totalWeight = 0;

    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = 0; j < n; ++j) {
            if (!inMST[j] && (u == -1 || minDist[j] < minDist[u])) u = j;
        }
        
        inMST[u] = true;
        totalWeight += minDist[u];
        
        for (auto& edge : graph[u]) {
            minDist[edge.first] = min(minDist[edge.first], edge.second);
        }
    }
    return totalWeight;
}