Алгоритм «Найти цикл в ориентированном графе» не работает в конкретной проблеме кода Leetcode. Ошибка- «AddressSanitizer: StackOverflow на определенный адрес» - PullRequest
0 голосов
/ 27 марта 2020

Ссылка на вопрос: расписание курсов leetcode

Вопрос явно сводится к выяснению, существует ли цикл. Я видел алгоритм для этого в канале YouTube Tushar Roy, но я изо всех сил пытаюсь реализовать его. Его идея заключалась в том, что если я столкнусь с элементом, уже присутствующим в стеке (исследуемых узлов), то возникнет цикл. Его реализация была в Java.

Его решение:
CycleInDirectedGraph. java

class Solution {
public:

    bool canFinish(int n, vector<vector<int>>& prerequisites) 
    {
        vector<vector<int>> adj(n,vector<int>());
        for(auto x:prerequisites)
        {
            adj[x[1]].push_back(x[0]);
        }
        unordered_set<int> whiteset;
        unordered_set<int> greyset;
        unordered_set<int> blackset;
        for(int i=0;i<n;i++)
        {
            whiteset.insert(i);
        }
        int c=0;
        while(!whiteset.empty())
        {
            if(dfs(*whiteset.begin(), greyset, whiteset, blackset,adj)) {
                c=1;
                break;
            }
        }
        if(c==1)
            return false;
        else
            return true;

    }
    bool dfs(int x,unordered_set<int> &greyset,unordered_set<int> &whiteset,unordered_set<int> &blackset,vector<vector<int>> &adj)
    {
        changeset(x,whiteset,greyset);
        for(auto y:adj[x])
        {
            if(blackset.find(y)!=blackset.end())
                continue;
            if(greyset.find(y)!=greyset.end())
                return true;
            if(dfs(x,greyset,whiteset,blackset,adj))
                return true;

        }
        changeset(x,greyset,blackset);
        return false;
    }
    void changeset(int x,unordered_set<int> &a,unordered_set<int> &b)
    {
        a.erase(x);
        b.insert(x);
    }
};
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...