Skip to content
Snippets Groups Projects
Select Git revision
  • 207018039b29bb136503bd7dcdbab3125afe15a2
  • devel default
  • master
  • fo
  • jirka/typing
  • fo-base
  • mj/submit-images
  • jk/issue-96
  • jk/issue-196
  • honza/add-contestant
  • honza/mr7
  • honza/mrf
  • honza/mrd
  • honza/mra
  • honza/mr6
  • honza/submit-images
  • honza/kolo-vs-soutez
  • jh-stress-test-wip
  • shorten-schools
19 results

upgrade-20210819.sql

Blame
  • do-sirky-matice.py 976 B
    #!/usr/bin/python3
    # Prohledávání grafu do šířky
    # Graf je reprezentovaný pomocí matice sousednosti
    
    from pprint import pprint
    from collections import deque
    
    # Načteme vstup: nejprve počet vrcholů, pak n řádků se sousedy jednotlivých vrcholů
    n = int(input())
    matice = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in input().split():
            j = int(j)
            matice[i][j] = 1
    
    # Pro kontrolu vypíšeme reprezentaci grafu (pprint = pretty print)
    pprint(matice)
    
    # Prohledávání do šířky
    def prohledej(v0):
        byl_jsem = [False] * n
        byl_jsem[v0] = True
        vzdalenost = [None] * n
        vzdalenost[v0] = 0
        fronta = deque()
        fronta.append(v0)
    
        while fronta:
            u = fronta.popleft()
            print(u, vzdalenost[u])
            for v in range(n):
                if matice[u][v] == 1 and not byl_jsem[v]:
                    byl_jsem[v] = True
                    vzdalenost[v] = vzdalenost[u] + 1
                    fronta.append(v)
    
    prohledej(3)