Not All Roads Lead There

For each node, we count and store the number of ways it can reach the final node. Let $paths(i)$ be the number of ways to reach the final node. The number of ways for node $i$ to reach the final node is the sum of the number of ways of $i$ 's children to reach the final node. Mathematically, this is

$path(i) = \sum_{j\in child(i)} path(j)$

Arriving at this equation we know that we must find $path(i)$ in the correct order, ie if we haven't compute the $path(j)$ we cannot compute $path(i)$ . To deal with this, Agnishom's idea is to get the topological sort and compute $path()$ according to that order. The definition of topological sort is that all children will be computed first before any of their parents, hence we will not miss out any children's $path()$ . My solution is to straightly compute from the beginning node and recursively find its way to the final node - the idea of Depth-First Search.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
using namespace std;

vector<int> adjList[35];
long long path[35];

// pay attention
void dfs(int node = 1) {
    if (node == 30)         // base case, 1 by default
        dp[node] = 1;
    if (path[node] != 0)    // compute already
        return;

    for (int i = 0; i < adjList[node].size(); i++) {
        int child = adjList[node][i];

        dfs(child);

        path[node] += path[child];
    }
}

int main() {

    for (int i = 0, u, v; i < 104; i++) {
        cin >> u >> v;

        adjList[u].push_back(v);
    }

    dfs();

    cout << path[1] << endl;

    return 0;
}

Let us first parse the edge list to a more suitable form:

1
2
3

children = [[] for i in xrange(31)]
for edge in edgeList:
    children[edge[0]].append(edge[1])

Our idea is this, the number of paths from vertex $i$ to the sink is equal to the sum of the number of paths from each of the children of vertex $i$ to the sink. So, we could work backwards from the sink to the source adding up the number of paths at each step.

But how do we know that we've already computed the number of paths for each of the children of a particular node? To do that we approach the computation of reverse topological order of the vertices. (Recall that a topological ordering is a permutation of the vertices such that if there is a directed edge $uv$ , $u$ appears after $v$ in the ordering).

Without full details on the topological sorting, here is how we implement it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def topoSort(children,N):
    L = []
    visited = [False for i in xrange(N+1)]
    def visit(u):
        if visited[u] == 'temp':
            raise Error
        if visited[u] == False:
            visited[u] = 'temp'
            for v in children[u]:
                visit(v)
            visited[u] = True
            L.append(u)
    for u in xrange(1,31):
        if visited[u] == False:
            visit(u)
    L.reverse()
    return L

And here is the main code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def countPaths(source, sink, children, N):
    topo = topoSort(children, N)
    sourceIndex, sinkIndex = map(topo.index,(source,sink))
    if sourceIndex > sinkIndex:
        return 0
    nPaths = [0 for i in xrange(N+1)]
    nPaths[sink] = 1
    i = sinkIndex
    while i != sourceIndex: 
        i -= 1
        for j in children[topo[i]]:
            nPaths[topo[i]] += nPaths[j]
    return nPaths[source]

print countPaths(1,30,children,30)

Deep first exploration in python 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

graph = {}
nbpath = 0
def initgraph():   
    f = open('graph.txt')
    content = f.read().split('\n')
    f.close()
    for  str in content:
        [i, j] = [int(s) for s in str.split(" ")]
        if i in graph:
            graph[i].append(j)
        else:
            graph[i] = [j]

def godeep(city):
    global nbpath
    if city == 30:
        nbpath += 1
    elif city in graph:
        for x in graph[city]:
            godeep(x)

def solve(graph):
    "Not All Roads Lead There"
    initgraph() 
    godeep(1)
    return nbpath

print(solve(graph))