Sí.
Use dfs para crear un árbol dfs y encontrar las copias de seguridad (digamos que forman el conjunto A). Si hay un nodo común en todos los bordes de A, la eliminación de ese nodo convertirá su SCC en DAG.
pseudocódigo:
dfs (nodo n)
para i en la lista de adyacencia de n:
si no he visitado
marca que visité
dfs (i)
más
A. inserción (borde (i, n))
Tendrá que verificar si el nuevo gráfico está conectado (si lo desea).
Editar: Perdón por ese error en el código. Realmente estúpido de mi parte.
Edición 2: Tendremos que reducir el SCC a un nuevo SCC de modo que la eliminación de un solo borde signifique la pérdida de una conectividad sólida. Eso se puede hacer utilizando el algoritmo de Kosaraju y marcando todos los bordes.
Parte del algoritmo de Kosaraju:
Sea g el gráfico dado g ‘sea el gráfico de transposición del gráfico dado.
1. Tome cualquier nodo n en g y haga dfs en él, y marque todos los bordes.
2. Ahora, haga un dfs para el mismo nodo en g ‘y marque el reverso de todos estos bordes.
Ahora, todos los bordes marcados más todos los nodos forman el SCC requerido.
- ¿Qué causa que la implementación viable de Quicksort sea muy lenta?
- ¿Hay alguna manera de extraer la palabra principal de una lista de sinónimos que representa la lista?
- ¿Cuál es la forma lógica de resolver el problema SPOJ 'Palin'?
- Si un algoritmo se ejecuta en tiempo O (N), pero N no excede una constante, ¿puedo decir que el algoritmo se ejecuta en tiempo constante?
- ¿Qué algoritmo se pregunta en la entrevista de Google?
