C++ 3 graph sort solutions using different data structures


  • 0

    Using vector, 19ms:

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int>> parents(numCourses);
            int numChildren[numCourses]; memset(numChildren, 0, sizeof(numChildren));
            for (auto p : prerequisites) {
                parents[p.second].push_back(p.first);
                numChildren[p.first]++;
            }
            
            queue<int> sinks;
            for (int i = 0; i < numCourses; i++) {
                if (!numChildren[i]) { sinks.push(i); }
            }
            
            while (sinks.size()) {
                int cur = sinks.front(); sinks.pop();
                numCourses--;
                
                for (int p : parents[cur]) {
                    if (--numChildren[p] == 0) { sinks.push(p); }
                }
            }
            
            return !numCourses;
    }
    

    Using hash table, 59ms:

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            unordered_map<int, unordered_set<int>> parents, children;
            for (auto p : prerequisites) {
                parents[p.second].insert(p.first);
                children[p.first].insert(p.second);
            }
            
            int numChildren[numCourses]; memset(numChildren, 0, sizeof(numChildren));
            queue<int> sinks;
            for (int i = 0; i < numCourses; i++) {
                if (!(numChildren[i] = children[i].size())) { sinks.push(i); }
            }
            
            while (sinks.size()) {
                int cur = sinks.front(); sinks.pop();
                numCourses--;
                
                for (int p : parents[cur]) {
                    if (--numChildren[p] == 0) { sinks.push(p); }
                }
            }
            
            return !numCourses;
    }
    

    Using array, 56ms:

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
           bool isEdge[numCourses][numCourses]; memset(isEdge, false, sizeof(isEdge));
            int numChildren[numCourses]; memset(numChildren, 0, sizeof(numChildren));
            
            for (int i = 0; i < prerequisites.size(); i++) {
                int a = prerequisites[i].first, b = prerequisites[i].second;
                
                if (!isEdge[a][b]) {
                    isEdge[a][b] = true;
                    numChildren[a]++;
                }
            }
            
            queue<int> sinks;
            for (int i = 0; i < numCourses; i++) {
                if (!numChildren[i]) { sinks.push(i); }
            }
            
            int cnt = 0;
            while (!sinks.empty()) {
                int cur = sinks.front(); sinks.pop();
                cnt++;
                
                for (int i = 0; i < numCourses; i++) {
                    if (isEdge[i][cur] && --numChildren[i] == 0) { sinks.push(i); }
                }
            }
            
            return cnt == numCourses;
    }
    

Log in to reply
 

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