Compruebe si existe un ciclo entre los Nodes S y T en un gráfico no dirigido con solo S y T repitiendo

Dado un grafo no dirigido con N Nodes y dos vértices S & T , la tarea es verificar si existe o no un ciclo entre estos dos vértices, de modo que ningún otro Node excepto S y T aparezca más de una vez en ese ciclo. Escriba Sí , si existe, de lo contrario, escriba No. 

Ejemplo:

Entrada:  N = 7, bordes[][] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 2}, { 2, 6}, {6, 0}}, S = 0, T = 4
Salida: No
Explicación: 

El Node 2 aparece dos veces, en el único ciclo que existe entre 0 y 4

Entrada: N = 6, bordes[][] = {{0, 1}, {0, 2}, {2, 5}, {3, 1}, {4, 5}, {4, 3}}, S = 0, T = 3
Salida: Sí
Explicación: 

El ciclo entre 0 y 3 es: 0->1->3->4->5->2->0

Acercarse:

Si existe un camino de regreso de T a S que no tiene vértices del camino usado para viajar a T desde S, entonces siempre habrá un ciclo tal que ningún otro Node excepto S y T aparezca más de una vez. Ahora, para resolver el problema, siga los pasos a continuación:

1. Cree una array visitada de tamaño n (donde n es el número de Nodes) e inicialícela con todo 0.
2. Inicie una búsqueda en profundidad desde S y coloque T como destino.
3. Cambie el valor 0 del Node actual a 1, en la array visitada para mantener el seguimiento de los Nodes visitados en esta ruta.
4. Si no es posible llegar a T , entonces no hay forma de que exista un ciclo simple entre ellos. Entonces, imprima No.
5. Si se alcanza T , cambie el destino a S y continúe con la búsqueda en profundidad. Ahora , los Nodes ya visitados no se pueden volver a visitar excepto S.
6. Si se alcanza S , imprima Sí, de lo contrario , No.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to create graph
void createGraph(vector<vector<int> >& graph,
                 vector<vector<int> >& edges)
{
    for (auto x : edges) {
 
        // As it is an undirected graph
        // so add an edge for both directions
        graph[x[0]].push_back(x[1]);
        graph[x[1]].push_back(x[0]);
    }
}
 
bool findSimpleCycle(int cur,
                     vector<vector<int> >& graph,
                     int start, int dest,
                     vector<bool>& visited,
                     bool flag)
{
 
    // After reaching T, change the dest to S
    if (!flag and cur == dest) {
        dest = start;
        flag = 1;
    }
 
    // If S is reached without touching a
    // node twice except S and T,
    // then return true
    if (flag and cur == dest) {
        return true;
    }
 
    bool ans = 0;
    visited[cur] = 1;
    for (auto child : graph[cur]) {
 
        // A node can only be visited if it
        // hasn't been visited or if it
        // is S or t
        if (!visited[child] or child == dest) {
            ans = ans
                  | findSimpleCycle(
                        child, graph, start,
                        dest, visited, flag);
        }
    }
 
    // Change visited of the current node
    // to 0 while backtracking again so
    // that all the paths can be traversed
    visited[cur] = 0;
 
    return ans;
}
 
int main()
{
    int nodes = 7;
    vector<vector<int> > edges
        = { { 0, 1 }, { 1, 2 }, { 2, 3 },
            { 3, 4 }, { 4, 5 }, { 5, 2 },
            { 2, 6 }, { 6, 0 } };
    int S = 0, T = 4;
 
    // To store the graph
    vector<vector<int> > graph(nodes);
 
    // To keep track of visited nodes
    vector<bool> visited(nodes);
    createGraph(graph, edges);
 
    // If there exists a simple
    // cycle between S & T
    if (findSimpleCycle(S, graph,
                        S, T, visited, 0)) {
        cout << "Yes";
    }
 
    // If no simple cycle exists
    // between S & T
    else {
        cout << "No";
    }
}

# Function to create graph
def createGraph(edges, N):
    graph = list([] for _ in range(N))
    for node1, node2 in edges:
 
        # As it is an undirected graph,
        # add an edge for both directions
        graph[node1].append(node2)
        graph[node2].append(node1)
 
    return graph
 
 
def findSimpleCycle(cur,
                    graph,
                    start,  dest,
                    visited,
                    flag):
 
    # After reaching T, change the dest to S
    if ((not flag) and cur == dest):
        dest = start
        flag = True
 
    # If S is reached without touching a
    # node twice except S and T,
    # then return true
    if (not flag and cur == dest):
        return True
 
    # first guess is that there is no cycle
    # so ans is False.
    # if we find one cycle, ans will be true
    # and then returned .
    ans = False
 
    # mark node as visited in this path
    visited[cur] = True
 
    for child in graph[cur]:
 
        # A node can only be visited if it
        # hasn't been visited or if it
        # is S or t
        if (not visited[child]) or child == dest:
            ans = ans or findSimpleCycle(
                child, graph, start,
                dest, visited, flag)
 
    # Change visited of the current node
    # to 0 while backtracking again so
    # that all the paths can be traversed
    visited[cur] = False
 
    return ans
 
 
if __name__ == "__main__":
 
    N = 7  # number of nodes
    edges = [[0, 1], [1, 2], [2, 3],
             [3, 4], [4, 5], [5, 2],
             [2, 6], [6, 0]]
    S = 0
    T = 4
 
    # To keep track of visited nodes
    visited_array = list(False for _ in range(N))
 
    # If there exists a simple
    # cycle between S & T
    if (findSimpleCycle(cur=S, graph=createGraph(edges, N),
                        start=S, dest=T,
                        visited=visited_array,
                        flag=0)):
        print("Yes")
 
    # If no simple cycle exists
    # between S & T
    else:
        print("No")

<script>
// Javascript program for the above approach
 
 
// Function to create graph
function createGraph(graph, edges) {
  for (x of edges) {
 
    // As it is an undirected graph
    // so add an edge for both directions
    graph[x[0]].push(x[1]);
    graph[x[1]].push(x[0]);
  }
}
 
function findSimpleCycle(cur, graph, start, dest, visited, flag) {
 
  // After reaching T, change the dest to S
  if (!flag && cur == dest) {
    dest = start;
    flag = 1;
  }
 
  // If S is reached without touching a
  // node twice except S and T,
  // then return true
  if (flag && cur == dest) {
    return true;
  }
 
  let ans = 0;
  visited[cur] = 1;
  for (child of graph[cur]) {
 
    // A node can only be visited if it
    // hasn't been visited or if it
    // is S or t
    if (!visited[child] || child == dest) {
      ans = ans
        | findSimpleCycle(
          child, graph, start,
          dest, visited, flag);
    }
  }
 
  // Change visited of the current node
  // to 0 while backtracking again so
  // that all the paths can be traversed
  visited[cur] = 0;
 
  return ans;
}
 
 
let nodes = 7;
let edges = [[0, 1], [1, 2], [2, 3],
[3, 4], [4, 5], [5, 2],
[2, 6], [6, 0]];
let S = 0, T = 4;
 
// To store the graph
let graph = new Array(nodes).fill(0).map(() => []);
 
// To keep track of visited nodes
let visited = new Array(nodes);
createGraph(graph, edges);
 
// If there exists a simple
// cycle between S & T
if (findSimpleCycle(S, graph,
  S, T, visited, 0)) {
  document.write("Yes");
}
 
// If no simple cycle exists
// between S & T
else {
  document.write("No");
}
 
// This code is contributed by saurabh_jaiswal.
</script>

No

Complejidad temporal: O(N!). Como podemos ver en este algoritmo, todos los caminos se pueden recorrer, en el peor de los casos, vamos a recorrer todos los caminos para encontrar uno que funcione, consulte este artículo: https://www.geeksforgeeks.org/count-possible- caminos-dos-vértices/
Espacio auxiliar: O(N^2)