No estoy seguro de qué código hace referencia específicamente, pero deduzco de él, y probablemente sea muy similar a esto de todos modos. Debido a que Disc[v] es el tiempo de descubrimiento del nodo v (dado el nombre “Disco”, pero podría usar solo la profundidad de depth[v] del nodo v ) y low[v] es el tiempo de descubrimiento mínimo (profundidad) de Todos los nodos a los que existe un borde directo desde algún nodo del subárbol de v (incluido v ). Si usa la fórmula low[u] = min(low[u], Disc[v]) , entonces está calculando exactamente eso, y esto es lo que necesita (el criterio es que si low[u]==Disc[u] , entonces u y su padre en el árbol DFS están en diferentes SCC). Sin embargo, si usa la fórmula low[u] = min(low[u], low[v]) , estaría calculando “el tiempo mínimo de descubrimiento (profundidad) de todos los nodos accesibles desde v “, pero esto ya no no funciona, porque puede encontrar de esta manera un camino que primero desciende de v , luego sube a la “raíz” de su SCC, luego baja de allí a otro SCC, luego sube de allí a la raíz de ese otro SCC, y así sucesivamente, porque esta definición de low[v] es totalmente recursiva.
También puede ver este video y el siguiente para otro algoritmo para calcular SCC.
- Cómo encontrar si un número dado es primo o no
- ¿Puedes explicar la prueba del postulado de Bertrand a un completo idiota?
- ¿Cuáles son las aplicaciones de las estructuras de datos?
- ¿Hay algún patrón dentro de la secuencia dada?
- ¿Cómo planificarías un campamento de algoritmos y estructuras de datos de un mes?
