Help! can't see the difference of my code with...


  • 0
    7

    https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions

    I compared my code with this solution, and tried to change many ways of putting the test for current and visited, but I found nothing. I'm so confused now about why I get TLE. I end up adding the test everywhere, but it is still TLE.

    Some gentle person that could help me? Thanks a lot!

    class Solution {
        
        bool ver(vector<vector<int> > rec,vector<bool>& visited,vector<bool>& current,int cur){
            if(current[cur])return false;
            if(visited[cur])return true;
            current[cur]=true;
            for(int i=0;i<rec[cur].size();i++){
                if(current[rec[cur][i]])return false;
                if(visited[rec[cur][i]])continue;
                if(!ver(rec,visited,current,rec[cur][i]))return false;
            }
            current[cur]=false;
            visited[cur]=true;
            return true;
        }
    public:
        bool canFinish(int n, vector<pair<int, int>>& pre) {
            vector<vector<int> > rec(n,*new vector<int>());
            vector<bool> visited(n,false);
            vector<bool> current(n,false);
            for(auto i:pre){
                rec[i.second].push_back(i.first);
            }
            for(int i=0;i<n;i++){
                if(visited[i])continue;
                if(!ver(rec,visited,current,i))return false;
            }
            return true;
        }
    };
    

  • 0

    @70664914 Your solution has two major problems:

    • bad variable names
    • complicated logic behind it

    Here is a solution I wrote long before, hope it can be helpful

    class Solution {
    private:
        bool isCycled(int n, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& path){
            if(visited[n]) return false;
            path[n] = visited[n] = true;
            for(auto next: graph[n])
                if(path[next] || isCycled(next, graph, visited, path)) return true;
            path[n] = false;
            return false;
        }
    public:
        bool canFinish(int n, vector<pair<int, int>>& pres) {
            vector<vector<int>> graph(n);
            for(auto& pair: pres)
                graph[pair.second].push_back(pair.first);
            vector<bool> visited(n, false), path(n, false);
            for(int i = 0; i < n; ++i)
                if(!visited[i] && isCycled(i, graph, visited, path)) return false;
            return true;
        }
    };
    

  • 0
    7

    Thanks, but I don't understand. In fact, my question is exactly how different is my solution from yours. As I said, I end up adding tests everywhere to help cut down the complexity, but for example, my original my code below, isn't it exactly the same logic as yours?
    rec record for edges
    current current points on the path
    cur current node

    Thanks

    class Solution {
        
        bool ver(vector<vector<int> > rec,vector<bool>& visited,vector<bool>& current,int cur){
            if(current[cur])return false;
            if(visited[cur])return true;
            current[cur]=true;
            for(int i=0;i<rec[cur].size();i++){
                if(!ver(rec,visited,current,rec[cur][i]))return false;
            }
            current[cur]=false;
            visited[cur]=true;
            return true;
        }
    public:
        bool canFinish(int n, vector<pair<int, int>>& pre) {
            vector<vector<int> > rec(n,*new vector<int>());
            vector<bool> visited(n,false);
            vector<bool> current(n,false);
            for(auto i:pre){
                rec[i.second].push_back(i.first);
            }
            for(int i=0;i<n;i++){
                if(!ver(rec,visited,current,i))return false;
            }
            return true;
        }
    };
    

  • 1

    @70664914 Your next explanation is much better but still your bad variable names are really confusing sometimes.

    After some digging, I found out that the actual problem in your solution is this:

    bool ver(vector<vector<int> > rec,vector<bool>& visited,vector<bool>& current,int cur)

    you should use reference for rec instead of directly passing it to the function which will result in deep-copy each time invoking the function. Change it to the following declaration format will solve the TLE problem.

    bool ver(vector<vector<int> >& rec,vector<bool>& visited,vector<bool>& current,int cur)


  • 0
    7

    @LHearen YES!!!! Thanks!!!!! Your digging helps absolutely!!!! Thanks for your help!


Log in to reply
 

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