Three intuitive topological methods enclosed with a DFS in cpp


  • 0
    class Solution
    {
    private:
        bool isCycled(const vector<vector<int>>& graph, int label, vector<bool>& visited, vector<bool>& in_path)
        {
            if(visited[label]) return false; //avoid re-checking the nodes visited in previous paths; 
            visited[label] = true; //each node visited should be labelled as visited avoiding further checking;
            in_path[label] = true; //should be labelled as visited for the current path;
            for(int neighbor: graph[label])
                if(in_path[neighbor] || isCycled(graph, neighbor, visited, in_path)) return true;
            in_path[label] = false; //restored to its unvisited state for another branch of the same starting node;
            return false;
        }
    public:
        //AC - 24ms - DFS method;
        bool canFinish(int num, vector<pair<int, int>> pres)
        {
            vector<vector<int>> graph(num);
            for(auto& pair: pres)
            graph[pair.second].push_back(pair.first);
            vector<bool> visited(num, false), in_path(num, false);
            for(int i = 0; i < num; i++)
                if(!visited[i] && isCycled(graph, i, visited, in_path)) return false;
            return true;
        }
    
        //AC - 320ms - topological sorting method;
        bool canFinish(int num, vector<pair<int, int>> pres)
        {
            unordered_map<int, vector<int>> graph;
            vector<int> indegrees(num, 0);
            for(auto& pair: pres)
            {
                graph[pair.second].push_back(pair.first);
                indegrees[pair.first]++;
            }
            while(graph.size())
            {
                int i = 0;
                for(; i < num; i++)
                    if(graph.count(i) && indegrees[i]==0) break;
                if(i == num) return false;
                for(int neigh: graph[i])
                    indegrees[neigh]--;
                graph.erase(i);
            }
            return true;
        }
    };

  • 0

    Topological method can be further optimised in this special problem using vector instead of map.


    class Solution
    {
    public: 
        //AC - 36ms - using vector instead of unordered_map to accelerate;
        bool canFinish(int num, vector<pair<int, int>> pres)
        {
            vector<vector<int>> graph(num);
            vector<int> indegrees(num, 0);
            for(auto& pair: pres)
            {
                graph[pair.second].push_back(pair.first);
                indegrees[pair.first]++;
            }
            for(int  j = 0; j < num; j++)
            {
                int i = 0;
                for(; i < num; i++)
                    if(!indegrees[i]) break;
                indegrees[i] = -1; //avoid re-checking;
                if(i == num) return false;
                for(int neigh: graph[i])
                    indegrees[neigh]--;
            }
            return true;
        }
    };

  • 0

    Actually using BFS and topological method can be the fastest, so there it is.


    class Solution {
    public:
        //AC - 20ms;
        bool canFinish(int num, vector<pair<int, int>>& pres) {
            vector<vector<int>> graph(num);
            vector<int> indegrees(num, 0);
            queue<int> toVisit;
            int count = 0;
            for(auto& pair: pres)
            {
                graph[pair.second].push_back(pair.first);
                indegrees[pair.first]++;
            }
            for(int i = 0; i < num; i++)
                if(!indegrees[i]) toVisit.push(i);
            while(!toVisit.empty())
            {
                int start = toVisit.front();
                toVisit.pop();
                for(auto n: graph[start])
                    if(--indegrees[n] == 0) toVisit.push(n);
                count++;
            }
            return count==num;
        }
    };

Log in to reply
 

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