TART - Tarjanのアルゴリズム

いくつかの競争的プログラミングを実践している間、グラフ理論の興味深いサブセクションに遭遇しました.
有向グラフにおいて、強接続コンポーネントは、SCCの各々のノードがSCCの全ての他のノードにパスを有することができるように、エッジを有するノードである.これらのsccsを1つのタルジャンのアルゴリズムと呼ばれる使用することができます見つけるために!
Tarjanのアルゴリズムは、1つのDFSパスO(V + E)時間を伴う有向グラフのSCCを見つけることができるアルゴリズムであり、スタックO(V)空間を使用する.ここで、Vはノード数、Eはエッジ数である.

それが動作する方法は、2つのリストを追跡することですdiscovery and low_link これはノード数の長さです.Tarjanのアルゴリズムは、SCCでどのノードがカウントされるかを記憶するためにスタックを使用するので正しく動作します.これがなければ、グラフ上でDFSを実行することができます.これは、グラフに実際にあるものより少ないSCCSを見つけるようにします.
スタックは、SCCに既に含まれているノードを追跡するために使用されます.したがって、スタックにあるノードに遭遇した場合、現在のSCCの一部でなければなりません.
アルゴリズムの高レベルの概要は次のとおりです
forループを使って全てのノードを通過し、ノードが見つからなかった場合はDFSをノード上で実行します.
あなたが訪問するようにノードを訪問するように、ノードをマークして、IDで各々のノードをマークして、そのノードdiscovery and low_link また、ノードをスタックにプッシュし、スタック上にあることを忘れないでください.
このアルゴリズムは、ノードの発見時間とlownumリンク値がこの順序で訪れた順番に等しいという考えを使用します.
ノードの隣人の全てを通してループし、訪問していないノードにDFSを実行します.
再帰から戻った後にlow_link 現在のノードの値は、自身と隣人の間のminに等しい.
また、隣人がスタック上にあるかどうかをチェックします.設定するlow_link 自分自身と隣人の発見時間の間の最小値への値.
すべての隣人をチェックした後、現在のノードのdiscovery 値はlow_link 値としては、SCCへのルートノードを意味します.現在のノードを含むすべてのノードのポップ.
最後に、あなたのlow_link リストはすべてのSCCSを持っている必要があります!

理論的性質

明らかに、このアルゴリズムはSCCが方法で最大であるという事実から働きます.そして、あなたがSCCを見つけるならば、それの中にもう一つのSCCがないということを保護します.アルゴリズムのもう一つの有用な特性は、SCCがその後継者のどれかの前に識別されないということです.

実装

ここではTarjanのアルゴリズムの私の実装です!

class TarjansGraph {
    public:
        inline static int UNVISITED = -1;
        vector<int> *adj_list;
        int n;

        TarjansGraph(int size) {
            this -> n = size;
            adj_list = new vector<int>[size];
        }

        void addEdge(int u, int v) {
            adj_list[u].push_back(v);
        }

        void dfs(int at, vector<int> &ids, vector<int> &low_list, vector<bool> &onStack, stack<int> &myStack) {
            ids[at] = at;
            low_list[at] = at;
            onStack[at] = true;
            myStack.push(at);

            for(auto iter : adj_list[at]) {
                if(ids[iter] == UNVISITED){
                    dfs(iter, ids, low_list, onStack, myStack);
                    low_list[at] = min(low_list[at], low_list[iter]);
                }
                else if (onStack[iter]) {
                    low_list[at] = min(low_list[at], ids[iter]);
                }
            }

            if (ids[at] == low_list[at]) {
                while(myStack.top() != at){
                    int stack_node = myStack.top();
                    cout << stack_node << " ";
                    onStack[stack_node] = false;
                    myStack.pop();
                }

                int at_stack_node = myStack.top();
                cout << at_stack_node << endl;
                onStack[at_stack_node] = false;
                myStack.pop();
            }
        }

        void findSCCs() {
            vector<int> ids(this -> n, TarjansGraph::UNVISITED);
            vector<int> low_list(this -> n, 0);
            vector<bool> onStack(this -> n, false);
            stack<int> myStack;

            for(int i = 0; i < this -> n; i++){
                if (ids[i] == TarjansGraph::UNVISITED) {
                    dfs(i, ids, low_list, onStack, myStack);
                }
            }
            cout << "\n\n\n LOW LIST VALUES: ";
            for (int i = 0; i < this -> n; i++){
                cout << low_list[i] << " ";
            }
            cout << endl;
        }

};