No he resuelto este problema, pero acabo de darme cuenta del truco involucrado en esto. No estoy seguro de que esto lo haga, pero definitivamente reducirá la complejidad del tiempo. En los algoritmos DFS normales, la complejidad resulta ser O (V + E) si está implementando usando una lista de adyacencia. Ahora, si observa de cerca lo que significan los componentes conectados, ¡ un vértice aislado también es un componente conectado en sí mismo!
Este es el truco, supongo en esto. Cuando esté escaneando los bordes, solo haga un seguimiento de la cantidad de vértices únicos que tiene. Digamos que el número de vértices únicos resulta ser x. Ahora no necesita aplicar DFS para cada vértice porque eso le daría TLE. Solo necesita ver los vértices cubiertos en los bordes que nos han dado. A lo sumo 2 * M vértices únicos pueden estar allí (¿Por qué?). Entonces su complejidad DFS resultaría ser O (M). Si, por ejemplo, hemos descubierto que tenemos componentes conectados A fuera del conjunto de bordes dados y tenemos N – x vértices no cubiertos en los bordes, entonces el número total de componentes conectados, es decir, el número total de galletas necesarias es A + (N – X)
Feliz codificación !!
- ¿Cuál es el tipo de algoritmo utilizado para resolver el problema de 8 reinas?
- ¿Cuál es la diferencia entre un algoritmo genético y el recocido simulado?
- ¿Existe algún enlace de los algoritmos o técnicas más utilizados en la programación competitiva?
- ¿Cuál es la mejor fuente para aprender del algoritmo y la estructura de datos para principiantes?
- ¿Qué representa un estado en términos de programación dinámica?
