---
# System prepended metadata

title: AiSD - 10.03.2021
tags: [AiSD]

---

# AiSD - 10.03.2021

###### tags: `AiSD`

## Zadanie 1.1

### Liczba wierzchołków w T
```cpp=
function count_vertices(node)
    if(node == NULL)
        return 0;
    return 1 + count_vertices(node.left) + count_vertices(node.right);
```

### Maksymalna odległość między wierzchołkami w T
```cpp=
function diameter(tree)
    if (tree == NULL)
        return {0, 0};
        
    {leftDiameter, leftHeight} = diameter(tree.left);
    {rightDiameter, rightHeight} = diameter(tree.right);

    return {max(leftHeight + rightHeight + 1, leftDiameter, rightDiameter),
            max(leftHeight, rightHeight) + 1};
                   

```

## Zadanie 1.2

![](https://i.imgur.com/iIHGmvr.png)
*    ```c=
        procedure push_down(K[1..n], i)
            if log(i)%2 == 1 then:
                push_down_max(K[1..n], i)
            else:
                push_down_min(K[1..n], i)
            
        procedure push_down_min(K[1..n], i)
                    if 4*i<=n then:
                        m <- arg_min(K[4*i..4*i+3])
                        if K[m] < K[i] then:
                            swap K[m] and K[i]
                            push_down_min(K[1..n], m)
                    else if 2*i<=n then:
                        m <- arg_min(K[2*i..2*i+1])
                        if K[m] < K[i] then:
                            swap K[m] and K[i]

       procedure push_down_max(K[1..n], i):
            if 4*i<=n then:
                m <- arg_max(K[4*i..4*i+3])
                if K[m] > K[i] then:
                    swap K[m] and K[i]
                    push_down_max(K[1..n], m)
            else if 2*i<=n then:
                m <- arg_max(K[2*i..2*i+1])
                if K[m] > K[i] then:
                    swap K[m] and K[i]
                    
        

*    ```c=
        procedure min_del(K[1..n])
            K[1] <- K[n]
            push_down(K[1..n − 1], 1)

*    ```c= 
        procedure max_del(K[1..n])
            if K[2] >= K[3] then:
                K[2] <- K[n]
                push_down(K[1..n − 1], 2)
            else:
                K[3] <- K[n]
                push_down(K[1..n − 1], 3)


## Zadanie 1.3
```cpp=
vector<int> adj[N];
int indeg[N];

for(int i=0;i<n;i++){
    for(int x : adj[i]){
        indeg[x]++;
    }
}


min_heap<int> kopiec;
for(int i= 0;i<n;i++){
    if(indeg[i] == 0) kopiec.insert(i);
}

vector<int> ans;

while(ans.size() < n){
    int aktualny = kopiec.min();
    ans.append(aktualny);
    kopiec.delete_min();
    for(int x : adj[aktualny]){
        indeg[x]--;
        if(indeg[x] == 0){
            kopiec.insert(x);
        }
    }
}

return ans;


```

## Zadanie 1.4

```python=
countWays = [0]*n
visited = [0]*n
dist = [0]*n
G = [[]]*n


def prep(u, v):
    countWays[v] = 1
    visited[v] = 1

    dijkstra(dist, v)

    dfs(u)

    return countWays[u]


def dfs(w):
    visited[w] = true

    for neighbour in G[w]:
        if dist[neighbour] < dist[w]:
            if visited[neighbour] != true:
                dfs(neighbour)
            countWays[w] += countWays[neighbour]
    return
```

$countWays[w]$ - liczba sensownych dróg wychodzących z w do v.

