C++ 28ms solution, using topological sort


  • 2
    I
    struct Vertex {
        unordered_set<int> adj;
        int indegree;
        Vertex() : indegree(0) {}
    };
    
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<Vertex> vertices(numCourses, Vertex());
        for (auto& p : prerequisites) {
            if (vertices[p.first].adj.find(p.second) == vertices[p.first].adj.end()) {
                vertices[p.first].adj.emplace(p.second);
                vertices[p.second].indegree++;
            }
        }
        queue<int> q;
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices[i].indegree == 0) {
                q.push(i);
            }
        }
        int count = 0;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            count++;
            for (int i : vertices[cur].adj) {
                if (--vertices[i].indegree == 0) {
                    q.push(i);
                }
            }
        }
        return count == numCourses;
    }

  • 0
    Y

    @Irving_cl
    I modify your solution slightly as follows:

    class Solution {
    public:
    struct Vertex {
        unordered_set<int> adj;
        int indegree;
        Vertex() : indegree(0) {}
    };
    
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<Vertex> vertices(numCourses, Vertex());
        for (auto& p : prerequisites) 
        {
            if (vertices[p.first].adj.find(p.second) == vertices[p.first].adj.end()) 
            {
                vertices[p.first].adj.emplace(p.second);
                vertices[p.second].indegree++;
            }
        }
        queue<int> q;
        for (int i = 0; i < vertices.size(); i++) 
        {
            if (vertices[i].indegree == 0) 
            {
                q.push(i);
            }
        }
        int count = 0;
        while (!q.empty()) 
        {
            int cur = q.front();
            q.pop();
            count++;
            for (int i : vertices[cur].adj) 
            {
                if (vertices[i].indegree == 1) 
                //if (--vertices[i].indegree == 0) 
                {
                    vertices[i].indegree--;
                    q.push(i);
                }
            }
        }
        return count == numCourses;
    }
    };
    

    Then submission result is "Wrong Answer". I think i just modify "--i" to "i--". I don't know what's wrong.

    • list item

  • 0
    I

    OK. You mean the line that you commented right? There's a difference between 'i--' and '--i'. The first one is called postfix operation, and the second one is prefix operation. Prefix operation takes effect immediately, even when the variable is used in the same line. However, Postfix operation takes effect after the variable used if they are in the same line.
    Let's see an example:
    int a = 1;
    int b = --a;
    then a = 0, b = 0 because prefix '--' takes effect immediately.
    In contrast:
    int x = 1;
    int y = x--;
    then x = 0, y = 1 because 'x' was used, and post '--' takes effect after it was used.
    The problem in your code is that the subtraction doesn't take place. Each time we pop a node from the queue, we should subtract all its adjacent node's indegree by 1. However, if you write like this, the subtraction will only take place when the indegree equals 1. If you use prefix operation and put it in the if condition, the indegree will decrease 1 in each iteration.


  • 0
    M

    @yuluodi Hi, have you tried your modification? It is wrong because you should decrease the indegree before checking the vertex is root or not. So if you want more readable, at least the code should look like this:
    By the way @Irving_cl your solution is right and helpful!

    for (int i : vertices[cur].adj) 
            {
                vertices[i].indegree--;
                if (vertices[i].indegree == 1) 
                //if (--vertices[i].indegree == 0)
                {
                    q.push(i);
                }
            }

  • 0
    I

    @yuluodi
    OK. You mean the line that you commented right? There's a difference between 'i--' and '--i'. The first one is called postfix operation, and the second one is prefix operation. Prefix operation takes effect immediately, even when the variable is used in the same line. However, Postfix operation takes effect after the variable used if they are in the same line.
    Let's see an example:
    int a = 1;
    int b = --a;
    then a = 0, b = 0 because prefix '--' takes effect immediately.
    In contrast:
    int x = 1;
    int y = x--;
    then x = 0, y = 1 because 'x' was used, and post '--' takes effect after it was used.
    The problem in your code is that the subtraction doesn't take place. Each time we pop a node from the queue, we should subtract all its adjacent node's indegree by 1. However, if you write like this, the subtraction will only take place when the indegree equals 1. If you use prefix operation and put it in the if condition, the indegree will decrease 1 in each iteration.
    Forget to @you at first...


Log in to reply
 

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