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?

no offense but your code looks like you learned C++ from very poor tutorials. [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) and [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Though what I find most disturbing is that you are not using `std::vector` but manually managed dynamic c-arrays. Not only do you have a memory leak, but this also makes the code very hard to read — 463035818_is_not_an_ai, Feb 03 '22 at 12:17
The `else` part refers to two different things in the two variants. In the second form, the result of `isCyclicUtil()` affects whether `else` will be executed, not in the first. — 500 - Internal Server Error, Feb 03 '22 at 12:21
Unrelated, fix your memory leaks, ideally via [RAII](https://en.cppreference.com/w/cpp/language/raii), before you submit this to whatever power-that-be is awaiting it. — WhozCraig, Feb 03 '22 at 12:24
@500-InternalServerError you answer is the correct one. Please insert it as an answer, not a comment. — Nadav Har'El, Feb 03 '22 at 12:48
The && expression and the nested if have exactly the same effect, as && uses shortcut evaluation. As explained elsewhere, this is not the cause of your trouble. — , Feb 03 '22 at 14:58
@Yves Daoust: In the second block there is a nested if. So, if there is a condition where control of flow passes the first If statement and then fails in the inner If statement, the elseif statement will not be executed. But In the first block if first condition is true and second condition is false, then elseif condition will be executed. — Utsav, Feb 04 '22 at 03:35
@Utsav: I know that, of course. I am talking about the nested ifs vs. shortcut &&, not about the else. — , Feb 04 '22 at 08:01

molbdnilo · Accepted Answer · 2022-02-03T13:54:00.623

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;
}

nested if v/s && operator

1 Answers1