Модификация алгоритма для определения циклов в графе

Question

В следующем коде я проверяю, есть ли цикл цикла или нет, и он работает на 100%, но я хочу изменить его, вместо того, чтобы печатать. Да, я хочу, чтобы он напечатать первый узел повторения цикла. Так, например, если фактический график имеет цикл, а цикл равен 0,1,3,5,7,0, вместо да, я хочу напечатать 0. Или если цикл равен 1,3,5,7,8 , 1 он должен печатать 1. Если кто-нибудь получил идею, я был бы признателен, спасибо.

#include<iostream> 
#include <list> 
#include <limits.h> 
using namespace std; 

// Class for an undirected graph 
class Graph 
{ 
    int V; // No. of vertices 
    list<int> *adj; // Pointer to an array containing adjacency lists 
    bool isCyclicUtil(int v, bool visited[], int parent); 
public: 
    Graph(int V); // Constructor 
    void addEdge(int v, int w); // to add an edge to graph 
    bool isCyclic(); // returns true if there is a cycle 
}; 

Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 

void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
    adj[w].push_back(v); // Add v to w’s list. 
} 

// 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 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
     // If an adjacent is not visited, then recur for that adjacent 
     if (!visited[*i]) 
     { 
      if (isCyclicUtil(*i, visited, v)) 
       return true; 
     } 

     // If an adjacent is visited and not parent of current vertex, 
     // then there is a cycle. 
     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++) 
     if (!visited[u]) // Don't recur for u if it is already visited 
      if (isCyclicUtil(u, visited, -1)){ 
       return true; 
      } 

    return false; 
} 

// Driver program to test above functions 
int main() 
{ 
    int res=0; 
    int m, n; 
    cin >> m >> n; 

    Graph g1(m); 
    for(int i=0; i<n; i++) { 
     int q, r; 
     cin >> q >> r; 
     g1.addEdge(q, r); 
    } 

    g1.isCyclic()? cout << "Yes": 
    cout << "No"; 

    return 0; 
} 

Answer 1

Как только вы найдете цикл, посетив узел, который вы уже посетили, вы знаете, что этот узел является частью цикла. Затем вы можете просто выполнить поиск по глубине для самого узла. Как только вы его найдете, выведите все узлы в стеке.

Если вы хотите эффективно использовать код, вы также можете найти тактики, а затем вывести все узлы, пока не достигнете узла, где вы нашли этот цикл.

Answer 2

Найдите логический заказ (или просто упорядотите порядок поиска) и используйте хеш для повторения узлов и уже увиденных циклов. Номер стартового узла поиска печати. В зависимости от вашего порядка поиска ваши результаты могут отличаться.