Unexpected Behaviour with List in C++

April 23, 2023

I was writing a program for Euler circuit, but the program didn’t give the right output.

Adding a seemingly unrelated line of code got it to work. Can someone decode what just happened?

Snippet of the original program:

/* A is a vector of lists that, where A[i] is the list of edges from vertex i. */
/* perform checks for even degree, then find a non-isolated vertex to begin the tour */
int u;
for (u = 0; u < A.size() && A[u].empty(); u++)
while (!A[u].empty()) {
    cout << u << "->";
    int v = A[u].front();
    A[u].pop_front();
    u = v;
}
cout << u << endl;

The line that I added after the end of for loop:

cout << u << A[u].size() << endl;

>Solution :

Let me rewrite your snippet with more accurate indentation and some braces added for clarity:

int u;
for (u = 0; u < A.size() && A[u].empty(); u++)
{
    while (!A[u].empty()) {
        cout << u << "->";
        int v = A[u].front();
        A[u].pop_front();
        u = v;
    }
}
cout << u << endl;

Notice that the while loop is inside the for loop. But if we’re in the for loop, then A[u].empty() is true, so !A[u].empty() is false, so the while loop is never entered.

When you added a line "after" the for loop, you made that one line what the for loop executes:

int u;
for (u = 0; u < A.size() && A[u].empty(); u++)
{
    cout << u << A[u].size() << endl;
}
while (!A[u].empty()) {
    cout << u << "->";
    int v = A[u].front();
    A[u].pop_front();
    u = v;
}
cout << u << endl;

Now, you have the intended behavior: A for loop that increments u, followed by a separate while loop that acts on u.

To get the original behavior while still having the first for loop do nothing, actually give your for loop an empty body:

int u;
for (u = 0; u < A.size() && A[u].empty(); u++) { }
while (!A[u].empty()) {
    cout << u << "->";
    int v = A[u].front();
    A[u].pop_front();
    u = v;
}
cout << u << endl;