Print all verticies in graph's cycle

Question

I've tried according to this Algorithm to find and print simple cycle in complexity of O(n) on undirected graph. Did it in C++ according to my tutor and following is my code:

int parent[1000] = {0};
int status[1000] = {0};
bool oriented = true;

#include ...

using namespace std;
array<list<int>, 1000 + 1> g;


void PrintCycle(int v, int u) {
    do {
        printf("%d",u);
        u = parent[u];
    } while (u != v);
}

bool DFS_cycle(int u) {
    status[u] = 1;
    for (int v:g[u]) {
        if (status[v] == 0) {
            parent[v] = u;
            DFS_cycle(v);
        }
        if (status[v] == 1 && v != parent[u]) {
            PrintCycle(v,u);
        }
    }
    status[u] = 2;
}


int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int N, u, v;
    cin >> N;
    while (cin >> u >> v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    parent[1] = 1;
    DFS_cycle(1);
    return 0;
}

But it doesn't work for the following input: (First line is the number of vertices. Vertices are numbered from 1. After that each line describes an edge.)

8

3 1

3 4

3 2

2 5

2 6

6 7

6 8

What did I do wrong?

Answer 1

First of all you have used C++ not C.

For the given input there is no cycle. It doesn't print any cycle either. So it does work for the given input.

However your code has bug. If we add another edge (5,8) a cycle is formed (2 -> 5 -> 8 -> 6). But your code prints the cycle as (6 -> 8 -> 5).

Check out my code for your bug :

void PrintCycle(int v, int u) {
    while(u != v)
    {
        printf("%d ",u); // You didn't give any space after %d
        // It could not be possible to differentitate between '1''2'
        // and '12'

        u = parent[u];
    }

    printf("%d \n", v);

}

bool DFS_cycle(int u) {

    status[u] = 1;
    for (int v:g[u]) {
        if (status[v] == 0) {
            parent[v] = u;
            DFS_cycle(v);
        }
        else if (status[v] == 1 && v != parent[u]) { // It should be 'else if' NOT 'if'
            PrintCycle(v,u);
            break;
        }
    }
    status[u] = 2;
}

And it is a good idea to #define WHITE 0, #define GRAY 1 etc and then using WHITE, GRAY etc instead of using bare 1, 2 etc.