Тема: Количество путей в графе
Дан ориентированный связанный граф без циклов.
Как найти количество различных путей от вершины s в вершину t? и вывести их(все пути).
например дан граф:
4 - вершины
5 - ребер
1 4
1 2
1 3
2 4
3 4
Пусть s = 1, а t = 4, тогда кол-во путей различных будет 3и, это:
1 - 2 - 4
1 - 4
1 - 3 - 4
Пытался обходом в ширину найти, когда из любой другой вершины выходим на t тогда выписываем путь, но в этом случае может оказаться что смежные вершины могут уже быть помеченными, а если вообще не помечать то плохо получается((