циклы печати в неориентированном графике

Question

вот мои коды, обнаруживающие цикл в неориентированном графике

#include<iostream>
#include <list>
#include <vector>
#include <stack>
using namespace std;

class Graph {
    int V, index;
    const int N = 100000;
    list <int> * adj;
    vector<bool> visited;

    // parent stores the parent node of the visited node, this is used 
    // for finding cycle in an undirected graph

    vector<int> parent;

    bool isCycle;    
    
public:
    Graph(int V);

    ~Graph () {
        delete [] adj;
    }
    void addEdge(int src, int dst);
    void set_index();
    void DFS_isCycleUntil(int src);
    bool IsCyclePresent();
    void printCycles(int edges, int mark[], int& cyclenumber);

    
};

Graph::Graph(int V){
           this->V = V;
           adj = new list<int> [V];
           this->index = 0;
           visited.resize(V, false);
           parent.resize(V, -1);
           isCycle = false;
}

void Graph::set_index()
{
    this->index = 0;
}


void Graph::addEdge(int src, int dst) {
    adj[src].push_back(dst); // push back to add to the linked list
    adj[dst].push_back(src);
 }

void Graph::DFS_isCycleUntil(int src) {
    visited[src] = true;
    
    for (auto& adj_V: adj[src]) {
        if (!visited[adj_V]) {
            parent[adj_V]=src;
            DFS_isCycleUntil(adj_V);
        } else if(parent[src] != adj_V) {
            isCycle = true;
            return;
        }
    }
}

bool Graph::IsCyclePresent() {
    return isCycle;
}


int main()
{

    Graph gdfs(6);

    gdfs.addEdge(0, 1);
    gdfs.addEdge(1, 2);
    gdfs.addEdge(2, 3);
    gdfs.addEdge(3, 4);
    gdfs.addEdge(4, 5);
    gdfs.addEdge(5, 2);

    gdfs.DFS_isCycleUntil(0);
    cout << " Depth-first traversal for the given graph: "<<endl;
    cout << "cycle present: " << (gdfs.IsCyclePresent() ? "true" : "false")<< '\n';
    return 0;
}

Я хочу распечатать каждый обнаруженный цикл. Я видел несколько попыток от geekforgeek, но боюсь, что не могу последовать за ними ... это могло быть неправильно. Интересно, кто-нибудь мог бы предложить эффективный способ включения функции печати для распечатки пути всех обнаруженных циклов?

Answer 1

Мы можем вызывать printCycle всякий раз, когда мы встречаем цикл в DFS_isCycleUntil.

void printCycle(int cur, int par)
{
    if (cur == par)
    {
        cout << cur << endl;
        return;
    }
    cout << cur << "->";
    printCycle(parent[cur], par);
}

void Graph::DFS_isCycleUntil(int src) {
    visited[src] = true;

    for (auto& adj_V : adj[src]) {
        if (!visited[adj_V]) {
            parent[adj_V] = src;
            DFS_isCycleUntil(adj_V);
        }
        else if (parent[src] != adj_V) {
            isCycle = true;
            cout << adj_V << "->";
            printCycle(src, adj_V);
            return;
        }
    }
}