Zajecia 2

Zajecia 2

1. Zliczanie wierzcholkow na danej glebokosci:
from collections import deque
n = int(input())

G = [ [] for _ in range(n + 1) ]
for i in range(n - 1):
    a, b = map(int, input().split())
    G[ a ].append(b)
    G[ b ].append(a)

x = int(input())

Q = deque()
odwiedzone = set()
glebokosci = [ 0 for _ in range(n + 1) ]

odwiedzone.add( 1 )
Q.append( (1,0) )

while( len(Q) > 0 ):
    act = Q.popleft()
    glebokosci[ act[ 1 ] ] += 1

    for w in G[ act[ 0 ] ]:
        if not w in odwiedzone:
            odwiedzone.add( w )
            Q.append( (w, act[ 1 ] + 1) )

print(glebokosci[ x - 1 ])


2. two-pointery
Sprawdzanie czy istnieje spojny podciag w tablicy o sumie x

tab = [1,1,3,4,7,7,8,9]
n = len(tab)

p1, p2 = 0, 0

x = 17
sum = 0
znaleziono = False
while p1 < n:
    while p2 < n and sum < x:
        sum += tab[ p2 ]
        p2 += 1

    if sum == x or p1 >= p2:
        if sum == x:
            znaleziono = True
        break
    sum -= tab[ p1 ]
    p1 += 1

if not znaleziono:
    print('Nie znaleziono\n')
else:
    print(sum)


3. Dalej two-pointery
Wybieranie z tablicy jak najwiekszej liczby elementow, gdzie
roznica miedzy najwiekszym a najmniejszym jest <= 5

n = int(input())
tab = list(map(int, input().split()))

tab.sort()

p1, p2 = 0,0
najdluzszy = 0
while p1 < n:
    while p2 < n and tab[ p2 ] - tab[ p1 ] <= 5:
        p2 += 1
    najdluzszy = max(najdluzszy, p2 - p1)
    p1 += 1

print(najdluzszy)


4. Wczytywanie labiryntu

fstream plik;
plik.open("maze.txt");

string x;
while( !plik.eof() ){
  getline(plik, x);
  MAZE.push_back( x );
}
plik.close();

for(auto m: MAZE) cout << m << endl;