Ссылка на вопрос: расписание курсов 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);
}
};