C++ 28ms BFS code that beats 100% submissions


  • 0
    R
     /** Check if a circle exists in a directed graph
     *  Topological sort to return a list of vertices
     *  Implement Kahn's algorithm for BFS
     *  Complexity O(V + E)
     */
    class Graph {
        int V;          // # vertices
        list<int> *adj;  // adjacent matrix
        int* indegree;  // in degree of vertices
    public:
        Graph(int V);
        void addEdge(int u, int V);
        vector<int> toposort();
    };
    
    Graph::Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
        indegree = new int [V];
        memset(indegree, 0, V*sizeof(int));
    }
    
    void Graph::addEdge(int u, int v) {
        adj[u].push_back(v);
        indegree[v]++;
    }
    
    vector<int> Graph::toposort() {
        vector<int> ret(V,-1);
        int retItr = V;
        queue<int> q;   //queue q to store all vertices with no incoming edge
        for (int i = 0; i < V; i++)
            if (indegree[i] == 0)
                q.push(i);
        while (!q.empty()) {
            int v = q.front(); q.pop(); ret[--retItr] = v;
            for (list<int>::iterator it = adj[v].begin(); it != adj[v].end(); it++) {
                //decrease the in degree of the vertice that is the other end of the edge
                if (--indegree[*it] == 0)    
                    q.push(*it);
            }
        }
        if (retItr > 0) {
            ret.clear();
            return ret;
        }// after BFS, if the grpah is still not empty, there exists at least one circle
        else return ret;
    }
    
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            Graph g(numCourses);
            for (int i = 0; i < prerequisites.size(); i++)
                g.addEdge(prerequisites[i].first, prerequisites[i].second);
            return g.toposort();       
        }
    };

Log in to reply
 

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