Redundant Connection I&IIを解決するアルゴリズムを検討する

12031 ワード

並列調査セット(Union-Find)は集合関係を処理するためのアルゴリズムであり,連通図に関する問題において非常に実用的である.基本的な操作には、集合の並列(Union)と、要素が属する集合の検索(Find)が含まれます.
アルゴリズムの構想は以下の通りである:各集合には、代表要素がある.同じセット内のすべての要素で、それらの代表要素は必然的に同じです.要素がどの集合に属するかを区別するには、その代表要素を見つけます.
そのストレージ構造は通常1次元配列(Nは要素の総数を表す):

int father[N + 1] = { 0 };

初期化は次のとおりです.

for (int i = 1; i <= N; i++) { father[i] = i; }

では、定義に基づいて、ある要素が存在する集合の代表要素を検索するための関数は、次のように実現できます.

int getFather(int x) {
    if (father[x] == x) {
        return x;
    } else {
        return getFather(father[x]);
    }
}

しかし,元素の数が大きい場合,複数回の再帰は明らかに効率が低い.では、「圧縮パス」の方法を導入できます.

int getFather(int x) {
    if (father[x] == x) {
        return x;
    }
    else {
        int xFather = getFather(father[x]);
        father[x] = xFather;
        return xFather;
    }
}

これにより,再帰のたびにfather[x]の値が更新され,圧縮経路の目的が達成され,複数回の再帰が回避される.この方式はO(n)の時間複雑度で実現された並列調査セットである.
検索操作を実現した後、その上で集合の並列操作を行うことができ、基本的に以下のように実現する.

void union(int x, int y) {
    int xFather = getFather(x);
    int yFather = getFather(y);
    father[yFather] = xFather;
}

すなわち,後の要素yをxが属する集合に組み込み,xとyがそれぞれ2つの集合の代表元であれば,xとyが存在する2つの集合を並べた操作である.
基本的にアルゴリズムをマスターして調べると、LeetCodeの684 Redundant Connectionと685 Redundant Connection IIをうまく解決できます.
684 Redundant Connection
In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1: Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like this: 1 /\ 2 - 3 Example 2: Input: [[1,2], [2,3], [3,4], [1,4], [1,5]] Output: [1,4] Explanation: The given undirected graph will be like this: 5 - 1 - 2 | | 4 - 3 Note: The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
入力はN個のノードがあり、連通し、無環の無方向図を与えた.図には余分なエッジがあり、このエッジを見つける必要があります.
セットのアルゴリズムを用いて,この問題を簡単に解決できる.ループ入力は、ループと同時に集合を構築します.1つのエッジが見つかった場合、その2つのエンドポイントはすでに同じセットに属しているので、このエッジは明らかに余分です.そうでなければ、並列操作を続行します.問題は複数の解がある場合に最後の1つを返すことを要求し,これらの余分なエッジを記録し,最後に更新されたエッジを返すだけでよい.コードは次のように実装されます.

class Solution {
public:
int father[1001] = { 0 };

int getFather(int node) {
    if (father[node] == node) {
        return node;
    }
    else {
        int nodeFather = getFather(father[node]);
        father[node] = nodeFather;
        return nodeFather;
    }
}

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    for (int i = 1; i <= 1000; i++) {
        father[i] = i;
    }
    vector<int> result;
    for (auto it = edges.begin(); it != edges.end(); it++) {
        int aFather = getFather(it->at(0));
        int bFather = getFather(it->at(1));
        if (aFather != bFather) {
            father[bFather] = aFather;
        }
        else {
            result.clear();
            result.push_back(it->at(0));
            result.push_back(it->at(1));
        }
    }
    return result;
}
};

一方、Redundant Connection IIでは、セットを調べた上で少し拡張する必要があります.
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, …, N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.
Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
Example 1: Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given directed graph will be like this: 1 /\ v v 2–>3 Example 2: Input: [[1,2], [2,3], [3,4], [4,1], [1,5]] Output: [4,1] Explanation: The given directed graph will be like this: 5 2 ^ | | v 4 Note: The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.
今回入力したのは方向図で、このようなノード(ルートノード)があり、他のすべてのノードがそのサブノードであることが規定されています.ルートノード(入力度0)以外のすべてのノードには、親ノードが1つしかありません(入力度1).入力には、このエッジが除去されると、得られる図こそ上記の条件に合致する図である.
問題の意味に基づいて、私たちは1つの結論を出すことができます:探し当てるこの辺が除去した後に、得た図はきっと条件に合っています.つまり、この辺は、原図の合法性を破壊している.
では、どのような図が条件に合わないのでしょうか.

にはループ図があります.ループ図には入度0のルートノードが存在しないためである.

には、2の入度を持つノードが存在する.余分なエッジを1本取り除くだけで条件に合った図になるので,入度2のノードが1つしか存在しない.その数は1にすぎず、入度は2にすぎません.

この2つの条件を決定した後,図にリングがある場合,リングの1つのエッジが除去されるというさらなる推論を得ることができる.入度2のノードが存在すると、そのノードをサブノードとする2つのエッジのうち、必ず1つが除去されるエッジである.上記の推論によれば、以下のアルゴリズムが得られる.

このアルゴリズムによれば、コード実装は以下のようになる.

class Solution {
public:
int father[1001] = { 0 };

int getFather(int node) {
    if (father[node] == node) {
        return node;
    }
    else {
        int nodeFather = getFather(father[node]);
        father[node] = nodeFather;
        return nodeFather;
    }
}

vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    for (int i = 1; i <= 1000; i++) {
        father[i] = i;
    }
    vector<int> resultA, resultB;
    int parent[1001] = { 0 };
    //      2   ，      A,B
    for (auto it = edges.begin(); it != edges.end(); it++) {
        if (parent[it->at(1)] == 0) {
            parent[it->at(1)] = it->at(0);
        }
        else {
            resultA.push_back(parent[it->at(1)]);
            resultA.push_back(it->at(1));
            resultB.push_back(it->at(0));
            resultB.push_back(it->at(1));
            it->clear();  //      B
        }
    }

    for (auto it = edges.begin(); it != edges.end(); it++) {
        if (it->empty()) {
            continue;
        }
        int aFather = getFather(it->at(0));
        int bFather = getFather(it->at(1));
        if (aFather == it->at(1)) {  //     
            if (resultA.empty()) {  //       2   
                return *it;
            }
            else {
                return resultA;
            }
        }
        father[bFather] = aFather;
    }
    return resultB;
}

};

各条件の判断手順に注意する.たとえば、図をループにする最後のエッジを直接取り除くことはできません.これにより,入度2のノードも存在する可能性があるからである.図中にループがあることを決定した後、入度2の接点があるか否かを優先的に判断し、ループの問題を考慮すべきである.

K短絡——A*アルゴリズム

3-sum問題を分析する(Three sum)