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;