Bfs topo sort in c++


  • 1
    O
    vector<int> findOrder(int nCrs, vector<pair<int, int>>& prqst) {
        
        int nprqst = prqst.size();
        
        vector<unordered_set<int> > links(nCrs); 
        vector<int> inDgr(nCrs,0);
        // construct directed links and compute in-degree of all nodes
        for (int i = 0; i < nprqst; i++) {
            if ( links[prqst[i].second].count(prqst[i].first) ) continue;
            links[prqst[i].second].insert(prqst[i].first);
            inDgr[prqst[i].first]++;
        }
        
        // find all nodes with 0 in-degree
        queue<int> topoQ; // can be replaced by stack, list, or vector,
        for (int i = 0; i < nCrs; i++) {
            if (inDgr[i]==0) topoQ.push(i);
        }
        
        int cnt = 0;
        vector<int> ret;
        
        while (!topoQ.empty()) {
            int cur = topoQ.front();
            ret.push_back(cur);
            cnt++;
            topoQ.pop();
            // add nodes to the queue whenever its in-degree hits 0
            for (auto it = links[cur].begin(); it != links[cur].end(); it++) {
                inDgr[*it]--;
                if (inDgr[*it]==0) topoQ.push(*it);
            }
        }
        // if all nodes are counted once, there is no cycle.
        if (cnt!=nCrs) return vector<int>();
        else return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.