Cómo verificar si existe una ruta simple entre los nodos a y b de modo que pase a través del nodo c

Si existe una ruta de a a c, y una ruta de c a b, entonces existe una ruta de a a b que pasa por c.

* Editar *: No noté la palabra simple en la pregunta.

Así es como lo haría entonces:

Mantenga una matriz visitada de bools que tenga en cuenta si el nodo i ha sido visitado o no.

Codifique una profundidad Primero busque desde el nodo a, solo va a los nodos no visitados y marca los nodos visitados cada vez que los alcanza (y no se visita cuando termina de alcanzarlos).

Cada vez que llegue al nodo b, verifique si el nodo c fue visitado usando la matriz visitada en O (1).

// booleano que se almacenará si existe una ruta simple entre ayb que pasa por c.
bool encontrado = falso;

int nbNodes, nbEdges;
int a, b, c;
const int MAX_NB_NODES = 1e5;
vector adj [MAX_NB_NODES];
bool visitó [MAX_NB_NODES];

dfs nulo (nodo int) {
if (visitado [nodo] || encontrado)
regreso;
visitado [nodo] = verdadero;
if (nodo == b) {
encontrado | = visitado [c];
regreso;
}
para (int vecino: adj [nodo])
dfs (vecino);
visitado [nodo] = falso;
}

bool pathExists (int A, int B, int C) {
fill_n (visitado, nbNodes + 1, falso);
encontrado = falso;
a = A, b = B, c = C;
dfs (a);
retorno encontrado;
}

Supongamos que puede verificar si existe una ruta entre los nodos x e y.

Use eso para verificar que hay una ruta de a a c. Si es así, verifique que haya una ruta de c a b. Si es así, existe una ruta de a a b a c.