обнаружение цикла в ориентированном графе с нерекурсивными dfs

Question

Мой код работает, но не для всех тестовых случаев.

Я пытаюсь создать «логический массив ifparent», содержащий запись пути, по которому я прохожу.

'логический массив посещений' ведет запись всех посещенных вершин.

Я использую стек для DFS.

//v is no of vertex, adj[] is the adjacency matrix
bool isCyclic(int v, vector<int> adj[])
{
    stack<int> st;
    st.push(0);

    vector<bool> visited(v, false);
    vector<bool> ifparent(v, false);
    int flag= 0;

    int s;
    while(!st.empty()){
        s= st.top();
        ifparent[s]= true;
        visited[s]=true;
        flag=0;

        for(auto i: adj[s]){
            if(visited[i]){
                if(ifparent[i])
                    return true;
            }
            else if(!flag){
                st.push(i);
                flag= 1;
            }
        }

        if(!flag){
            ifparent[s]= false;
            st.pop();
        }
    }

    return false;

}

Answer 1

Если вам нравится итеративный подход к обнаружению циклов с помощью DFS, я порекомендую вам небольшую реорганизованную версию вашего кода, где я пишу DFS более распространенным способом.

bool isCyclic(int V, vector<int> adj[]) {
  vector<bool> visited (V, false);
  vector<bool> on_stack (V, false);
  stack<int> st;

  for (int w = 0; w < V; w++) {

    if (visited[w])
      continue;
    st.push(w);

    while (!st.empty()) {
      int s = st.top();

      if (!visited[s]) {
        visited[s] = true;
        on_stack[s] = true;
      } else {
        on_stack[s] = false;
        st.pop();
      }

      for (const auto &v : adj[s]) {
        if (!visited[v]) {
          st.push(v);
        } else if (on_stack[v]) {
          return true;
        }
      }
    }
  }
  return false;
}