Polkujen määrä II

Muodosta syklitön suunnattu verkko, jonka solmut ovat $1,2,\dots,100$. Verkossa tulee olla $x$ erilaista polkua solmusta $1$ solmuun $100$. Verkossa saa olla korkeintaan $1000$ kaarta ja jokaisen kaaren tulee olla erilainen.

Toteuta tiedostoon paths2.py funktio create_edges, joka palauttaa verkon rakenteen listana kaaria tupleina. Esimerkiksi lista [(1, 2), (4, 5)] tarkoittaisi, että verkossa on kaksi kaarta $1 \rightarrow 2$ ja $4 \rightarrow 5$.

Voit olettaa, että $x$ on välillä $0 \dots 10^9$ kaikissa testeissä.

Voit testata funktiosi toimintaa kurssimateriaalissa olevan luokan CountPaths avulla. Tehtäväpohjassa metodin count_paths tulisi antaa tulos $123456789$, kun verkko on oikein muodostettu.

class CountPaths:
    # voit kopioida tämän luokan kurssimateriaalista

def create_edges(x):
    # TODO

if __name__ == "__main__":
    edges = create_edges(123456789)

    counter = CountPaths(range(1, 100 + 1))
    for edge in edges:
        counter.add_edge(edge[0], edge[1])
    print(counter.count_paths(1, 100)) # 123456789