Has complicado innecesariamente un problema muy simple.
En primer lugar, tenga en cuenta que todos los bordes van de oeste a este. Así, implícitamente, se nos da el tipo topológico de un gráfico dirigido. Esto nos ahorra el trabajo de hacer un dfs. Ahora podemos resolver el problema usando programación dinámica
Defina dos cantidades para cada vértice u:
- Algunos dicen que después de haber trabajado como desarrollador durante 2 años más o menos, debería poder pasar a un nuevo trabajo sin preguntas de algoritmos, ¿verdad?
- ¿Cómo se pueden realizar los pagos mediante algoritmos informáticos?
- ¿Cómo hace un algoritmo para hacer objetos en movimiento a partir de fotos?
- Cómo elegir el mejor algoritmo de aprendizaje profundo o paquete R para un conjunto de datos
- ¿Se puede usar la GPU para optimizar los algoritmos gráficos?
- f (u) = número de caminos de u a N
- g (u) = nivel máximo de alternativas para una ruta de u a N
El caso base para nuestra recurrencia será f (N) = g (N) = 1. Ahora, supongamos que hemos calculado f (v) yg (v) para todos v> u. Es fácil ver que f (u) = suma de f (v) para todos los v directamente accesibles desde u, contando la multiplicidad. Además, g (u) = f (u) + max (g (v)) para todos los v directamente accesibles desde u. Construir los valores de f y g para los vértices en orden decreciente será suficiente. g (1) es la respuesta final requerida.
Además, tenga en cuenta que no es necesario almacenar la multiplicidad de bordes por separado en un mapa. Es suficiente insertar entradas duplicadas en la lista de adyacencia. Esto asegurará que se agregue la multiplicidad mientras se calcula f pero no mientras se calcula g.
Finalmente, la solución es solo:
f[N]=g[N]=1; for(int i=N-1;i>0;i--) { for(int j=0;j<adjlist[i].size();j++) { f[i]+=f[adjlist[i][j]]; g[i]=max(g[i],g[adjlist[i][j]]); } g[i]+=f[i]; } return g[1]; 
