My accepted 340ms c++ solution use ListNodes, a custom data structure.


  • 0

    I created a custom data structure ’ListNodes’, the difference between 'ListNodes' and 'ListNode’ is that 'ListNodes' can point to multiple nodes.

    With this data structure, the prerequisites can be clearly represented, so we can use it to easily solve the problem.

    class Solution {
    public:
        bool canFinish(int numCourses, std::vector<std::vector<int> > &prerequisites) {
            std::vector<ListNodes> orders;
            for (int i = 0; i != numCourses; ++i) {
                ListNodes tmp(i);
                orders.push_back(tmp);
            }
            for (std::size_t i = 0; i != prerequisites.size(); ++i) {
                int after = prerequisites[i][0], pre = prerequisites[i][1];
                if (isNeed(&orders[after], pre))
                    return false;
                orders[pre].nexts.push_back(&orders[after]);
            }
            return true;
        }
    private:
    	typedef struct ListNodes {
    		int val;
    		std::vector<ListNodes *> nexts;
    		ListNodes(int x): val(x) {}
    	}ListNodes;
        bool isNeed(ListNodes *order, int val) {
            if (order->val == val)
                return true;
            for (std::size_t i = 0; i != order->nexts.size(); ++i)
                if (isNeed(order->nexts[i], val))
                    return true;
            return false;
        }
    };

Log in to reply
 

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