CodeBlanks Logo Icon CodeBlanks
Login Register

Summary - Advanced structures

Print union-find set merges in a mini task.

Summary - Advanced structures

In this group you learned three advanced structures: union-find, trie and segment tree. Each serves a different purpose: sets, prefixes, ranges.

Now you will write a function that deepens union-find. This summary unites the group's first concept in a single piece of code.

Practice count_sets function

Write count_sets(n). init_parent is given; do union(0,1) and union(2,3), return the number of distinct roots. Print 2 with print(count_sets(4)).

Starter code

solution.py
def init_parent(n):
    # Return parent array
    return list(range(n))
def count_sets(n):
    # Count distinct sets after unions

Sample solution

solution.py
def init_parent(n):
    # Return parent array
    return list(range(n))
def count_sets(n):
    # Count distinct sets after unions
    parent = init_parent(n)
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    def union(x, y):
        parent[find(x)] = find(y)
    union(0, 1)
    union(2, 3)
    roots = set(find(i) for i in range(n))
    return len(roots)
print(count_sets(4))

Expected output

2

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 What does union-find track?

  • A single node
  • Edge weights
  • Ranges
  • Sets Correct answer

Explanation: Union-find tracks sets.

2 find loop

Question 
while parent[x] ____ x:
Answer 
while parent[x] != x:

Explanation: != is right.

3 Summary - Advanced structures: match the terms

Term Meaning
union-find Sets
trie Prefixes
segment tree Ranges
parent Parent

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4