Union-Findデータ構造

基本的なテンプレート実装から始めましょう。

この種の問題は比較的単純で、主要な関数を正しく実装すれば解決できます。

int findRoot(int node){return (node == parent[node] ? node : parent[node] = findRoot(parent[node]));}

豆知識：多くの人はこの関数をFindやfindと命名しますが、私の場合はなぜfindRootという名前を使用しているのでしょうか？当初はFindとしていましたが、より明確にしたいと思いFind_Parentを使用していましたが、名称が長すぎると感じたため、FindとParentの頭文字を採用しfindRootとなりました。短くて覚えやすく、意味も明確で珍しい名前です！

拡張領域Union-Find

これは「敵の敵は味方」という概念を応用したものです。

例題：囚人の配置問題

この問題では貪欲法が有効です。衝突度が高いペアは同じグループに入れたくない。

各囚人をノードnodeとして表現し、その反対状態をnode + totalとします。

もしnodeAとnodeBを同じグループにしたくない場合、それぞれの反対状態と結びつけます。つまりエッジ(nodeA, nodeB + total)と(nodeA + total, nodeB)を作成します。

同じグループに配置せざるを得なくなるのは、nodeAとnodeA + totalが同じ集合に属している場合です。このとき、出力して終了します。

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e4+5, MAX_M = 1e5+5;
struct Edge{int src, dst, conflict;}edges[MAX_M];
int numPrisoners, numConflicts, group[2*MAX_N];

bool compareEdges(Edge e1, Edge e2){return e1.conflict > e2.conflict;}

int findRoot(int node){
    return (group[node] == node ? node : group[node] = findRoot(group[node]));
}

void unionGroups(int node1, int node2){
    if(findRoot(node1) != findRoot(node2))
        group[findRoot(node2)] = findRoot(node1);
    return;
}

int main(){
    cin >> numPrisoners >> numConflicts;
    for(int i = 1; i <= 2 * numPrisoners; i++)
        group[i] = i;
    
    for(int i = 1; i <= numConflicts; i++)
        cin >> edges[i].src >> edges[i].dst >> edges[i].conflict;
    
    sort(edges + 1, edges + numConflicts + 1, compareEdges);
    
    for(int i = 1; i <= numConflicts; i++){
        unionGroups(edges[i].src + numPrisoners, edges[i].dst);
        unionGroups(edges[i].src, edges[i].dst + numPrisoners);
        
        if(findRoot(edges[i].src) == findRoot(edges[i].src + numPrisoners) || 
           findRoot(edges[i].dst) == findRoot(edges[i].dst + numPrisoners)){
            cout << edges[i].conflict << "\n";
            return 0;
        }
    }
    cout << "0\n";
    return 0;
}

練習問題：ドアの問題

この問題も前述の問題と類似しています。

開いているドアに対しては(nodeX, nodeY)と(nodeX + m, nodeY + m)を結合し、閉じているドアに対しては(nodeX, nodeY + m)と(nodeX + m, nodeY)を結合します。

もしnodeZとnodeZ + mが同じ集合に含まれている場合、解は存在しません。

#include<bits/stdc++.h>
using namespace std;
const int MAX_NODES = 2e5+5;
int nodeCount, switchCount, connections[2][MAX_NODES], counter[MAX_NODES], parent[MAX_NODES];
bool initialState[MAX_NODES], isValid;

int findRoot(int node){
    return (parent[node] == node ? node : parent[node] = findRoot(parent[node]));
}

void unionNodes(int node1, int node2){
    parent[findRoot(node2)] = findRoot(node1);
    return;
}

int main(){
    cin >> nodeCount >> switchCount;
    isValid = true;
    
    for(int i = 1; i <= nodeCount; i++)
        cin >> initialState[i];
    
    memset(counter, -1, sizeof(counter));
    
    for(int i = 1; i <= switchCount; i++){
        int connectionNum;
        cin >> connectionNum;
        while(connectionNum--){
            int tempNode;
            cin >> tempNode;
            connections[++counter[tempNode]][tempNode] = i;
        }
    }
    
    for(int i = 1; i <= 2 * switchCount; i++)
        parent[i] = i;
    
    for(int i = 1; i <= nodeCount; i++){
        if(!initialState[i]){
            unionNodes(connections[0][i], connections[1][i] + switchCount);
            unionNodes(connections[0][i] + switchCount, connections[1][i]);
        } else {
            unionNodes(connections[0][i], connections[1][i]);
            unionNodes(connections[0][i] + switchCount, connections[1][i] + switchCount);
        }
    }
    
    for(int i = 1; i <= switchCount; i++)
        if(findRoot(i) == findRoot(i + switchCount))
            isValid = false;
    
    if(isValid)
        cout << "YES\n";
    else 
        cout << "NO\n";
    
    return 0;
}

食糧連鎖問題

この問題は三重拡張が必要で、node、node + total、node + 2 * totalの三つの状態が存在します。三種類の動物が循環的に捕食関係にあるため、三倍の拡張が必要です。

まとめ

Union-Find構造自体は単純ですが、さまざまな応用や変形を加えることで複雑さが増します。さまざまな手法や状況に対応する必要があります。

様々な応用方法や革新を継続的に探求することが重要です。