finding cycles in directed graph using algorithm design manual

Question

so, i am following algorithm design but the below algorithm implemented from the book, fails in the following e.g., is there an issue with this algo -

         bool directed = true;

         bool dfs(int v, 
         vector<vector<int>>& adjList,
         vector<bool>& discovered,
         vector<bool>& processed,
         vector<int>& parent)
{     
    bool ans = false;
    discovered[v] = true;

    for(auto x : adjList[v])
    {
        if(!discovered[x])
        {
            parent[x] = v;  
            ans |= dfs(x, adjList, discovered, processed, parent);
        }
        else if((!processed[x] && parent[v]!=x) || directed)
        {
            if(parent[x]!=v)
            {
                return true;
            }
        }
    }

    processed[v] = true;
    return ans;
}

This is called using =

 for(int i = 0; i < n; ++i)
    {
        if(!discovered[i])
        {
            dfs(i, adjList, discovered, processed, parent);
                
        }
    }

It fails for this e.g. =

is the algo wrong in the book algorithm design manual - the e.g. above prints it has a cycle?

it fails when it is exploring the edge - 2 -- > 3 at that time, parent[3] = 1 and therefore parent[3] != 2 and it returns true and says it has a cycle.

Full code = https://ideone.com/9o0trZ

Answer 1

Good Code, But there is logical error in line no. 57, 58 and 66 (in the code link)

Line no. 57:- check for edge case i < n-1

Line no. 58 and 62:- Return boolean value, returning answer doesn't give correct ans

i. case(in line 58): // Graph should be connected (single component) so return false (instead od ans)

ii. case(in line 62): If there are no cycles and the graph is connected, it's a valid tree so return true (instead of ans)

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int n;
    vector<vector<int>> adjList;
    bool directed = true; // Set to true for a directed graph
public:
    bool dfs(int v, vector<vector<int>>& adjList, vector<bool>& discovered,vector<bool>& processed,vector<int>& parent)
{
    bool ans = false;
    discovered[v] = true;

    for (auto x : adjList[v]) {
        if (!discovered[x]) {
            parent[x] = v;
            ans |= dfs(x, adjList, discovered, processed, parent);
        } else if ((!processed[x] && parent[v] != x) || directed) {
            if (parent[x] != v) {
                return true; // Found a back edge, indicating a cycle
            }
        }
    }

    processed[v] = true;
    return ans;
}

bool validTree(int n, vector<vector<int>>& edges) {
    this->n = n;
    adjList.resize(n);
    vector<bool> discovered(n, false);
    vector<bool> processed(n, false);
    vector<int> parent(n, -1);

    for (auto& x : edges) {
        adjList[x[0]].emplace_back(x[1]);
    }

    bool ans = false;
    for (int i = 0; i < n; ++i) {
        if (!discovered[i]) {
            ans |= (dfs(i, adjList, discovered, processed, parent));
            if (ans || i < n - 1) {
                return false; // Graph should be connected (single component)
            }
        }
    }

    return true; // If there are no cycles and the graph is connected, it's a valid tree
  }
};

int main() {
  int n = 4;
  vector<vector<int>> edges(n);
  edges[0] = {0, 2};
  edges[1] = {3, 0};
  edges[2] = {3, 1};
  edges[3] = {1, 2};
  Solution s;
  if(s.validTree(n, edges))
  {
      cout<<"True"<<endl;
  }
  cout <<"False"<< endl;

  return 0;
}

If this minute mistakes are corrected, then overall it's a good code.

Happy Coding

Regards

Rakshath U Shetty