nested if v/s && operator

Question

I am writing code in C++ for checking if a cycle is present in a given undirected graph or not. My code is this:-

#include <bits/stdc++.h>
using namespace std;

// Class for an undirected graph
class Graph
{
    
    // No. of vertices
    int V;

    // Pointer to an array
    // containing adjacency lists
    list<int> *adj;
    bool isCyclicUtil(int v, bool visited[], int parent);
public:

    // Constructor
    Graph(int V);

    // To add an edge to graph
    void addEdge(int v, int w);

    // Returns true if there is a cycle
    bool isCyclic();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    
    // Add w to v’s list.
    adj[v].push_back(w);

    // Add v to w’s list.
    adj[w].push_back(v);
}

// A recursive function that
// uses visited[] and parent to detect
// cycle in subgraph reachable
// from vertex v.
bool Graph::isCyclicUtil(int v, bool visited[], int parent)
{
    
    // Mark the current node as visited
    visited[v] = true;

    // Recur for all the vertices
    // adjacent to this vertex
    for(int i:adj[v])
    {
        
        // If an adjacent vertex is not visited,
        //then recur for that adjacent
        
        
//      if ((!visited[i])&&(isCyclicUtil(i, visited, v)))                //        1st block
//      {
//          return true;
//      }
      
        if (!visited[i]) {                                          //         2nd block
            if (isCyclicUtil(i, visited, v)) {
                return true;
            }
        }

        // If an adjacent vertex is visited and
        // is not parent of current vertex,
        // then there exists a cycle in the graph.
        else if (i != parent)
        return true;
    }
    return false;
}

// Returns true if the graph contains
// a cycle, else false.
bool Graph::isCyclic()
{
    
    // Mark all the vertices as not
    // visited and not part of recursion
    // stack
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper
    // function to detect cycle in different
    // DFS trees
    for (int u = 0; u < V; u++)
    {
    
        // Don't recur for u if
        // it is already visited
        if (!visited[u])
        if (isCyclicUtil(u, visited, -1))
            return true;
    }
    return false;
}

// Driver program to test above functions
int main()
{
    Graph g1(5);
    g1.addEdge(1, 0);
    g1.addEdge(0, 2);
    g1.addEdge(2, 1);
    g1.addEdge(0, 3);
    g1.addEdge(3, 4);
    g1.isCyclic()?
    cout << "Graph contains cycle\n":
    cout << "Graph doesn't contain cycle\n";

    Graph g2(3);
    g2.addEdge(0, 1);
    g2.addEdge(1, 2);
    g2.isCyclic()?
    cout << "Graph contains cycle\n":
    cout << "Graph doesn't contain cycle\n";
  
    Graph g3(4);
    g3.addEdge(1, 2);
    g3.addEdge(2, 3);
    g3.isCyclic()?
    cout << "Graph contains cycle\n":
    cout << "Graph doesn't contain cycle\n";

    return 0;
}

There are two labeled blocks in this code namely block 1 and block 2.

This code outputs correctly when I use the second block. But if I use first block instead of the 2nd block It prints something different.

My question is that Are the first block and second block code use different logic? If not then why block 1 prints different from 2nd block?

Answer 1

Think about the negation of your condition, as this affects when the else branch is executed.

In the commented-out code, it is

!(!visited[i] && isCyclicUtil(i, visited, v))

which is

visited[i] || !isCyclicUtil(i, visited, v)

and your entire conditional, testing the negated condition first, is equivalent to

if (visited[i] || !isCyclic(i, visited, v)) {
    if (i != parent)
        return true;
}
else {
    return true;
}

In the "live" code, the negation is

!(!visited[i])

which is

visited[i]

and the entire conditional is equivalent to

if (visited[i]) {
    if (i != parent) {
        return true;
    }
}
else if (isCyclicUtil(i, visited, v)) {
    return true;
}