[LeetCode]207. Course Scheduleカリキュラム

こちらはLeeTioNのブログです
タイトルリンク
原題の大まかな意味は,番号0からn−1までの課程があり,2次元配列を入力して2つの課程間の前置関係を表し,[0,1]は1番課程を修了しなければ0番課程を修了できないことを示す.問題は、授業の前置関係を与えて、この関係が合理的かどうかを判断することです.(例えば[[0,1],[1,0]]は矛盾したカリキュラム関係である)
少し考えてみると、授業間の前置関係を1つの図で表すことができることがわかります.この問題はトポロジーソートの典型的な応用である.まず無ループ図の概念を導入します
方向図のある任意の頂点がいくつかの方向エッジを介して自身に戻ることができない場合、この方向図を方向無ループ図(DAG)と呼ぶ.
概念トポロジのソートを追加します.
トポロジー順序付けは、図Gの任意の2つの頂点u、vに対してエッジu->vが存在する場合、シーケンス中のuは必ずvの前にあるように、無ループ図Gのすべての頂点を1つの線形シーケンスに並べ替えることである.このシーケンスはトポロジーシーケンスとも呼ばれる.
実はこの問題の本質は図を与えて、この図がトポロジー秩序であるかどうかを判断しましょう.
ここでは、初期の図では0の点、すなわち、データ構造、C言語の基礎など、課程の最も基礎的な課程(データ構造、C言語の基礎など)を修了し、図の中のすべての0の点を見つけた後、順番に1つのキューに入れ、キューの先頭から1つの点をループして抽出し、この点を図に入れてクエリーする必要があります.どの点がこの点によって指向されているかを検出し,これらの点の入度を順次1ずつ減らし,直観的に見ると,1つの入度が0の点を削除する操作であり,1を減らすたびに他のノードの入度を検出し,新しい入度が0の点が現れたらキューに入れ,キューが空になるまでループ往復する.
ループが終了すると、各ノードの入度が再度チェックされ、図がトポロジー秩序であれば、ループ操作ではすべての入度が0になります.トポロジー秩序でなければ,入度が0でない点,すなわちリングも存在する.
ここでは,ターゲットノードが指す点にアクセスするたびにBFSの考え方を用いる.
コードを記述するには、2つのコンテナ、1つの構築図、1つのノードのインデックス数をリアルタイムで記録し、コードを貼り付ける必要があります.

bool canFinish(int numCourses, vectorint, int>>& prerequisites) {//BFS
        vector<vector<int>> graph(numCourses, vector<int>(0));
        vector<int> inDegree(numCourses, 0);
        for(auto i : prerequisites){
            graph[i.second].push_back(i.first);
            inDegree[i.first]++;
        }//        
        queue<int> q;

        for(int i = 0; i < inDegree.size(); i++){
            if(inDegree[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int temp = q.front();
            q.pop();
            for(auto j : graph[temp]){
                inDegree[j]--;
                if(inDegree[j] == 0){
                    q.push(j);
                }
            }
        }
        for(int i = 0; i < inDegree.size(); i++){
            if(inDegree[i] ！= 0){
                return false;
            }
        }
        return true;
    }