RavnaryA Knowledge Platform
Colour theme

Card 06/ 07

Take the quiz

ExerciseDifficulty: Advanced3 min

Practice: Finding the Separate Networks in a Building

Cables join pairs of computers; how many separate networks are there, and which cable was redundant?

Computers joined by cables form networks, and union-find can count them and spot a cable that adds nothing. This exercise covers processing a list of cables with union-find, counting the separate networks that result, and naming the cable that joined two computers already connected.

Union-find stores a parent for each item; an item that is its own parent is a root, and each root stands for one group. find(x) follows parents to the root, and union(a, b) sets the parent of a's root to b's root. A cable is redundant when the two computers it joins could already reach each other through other cables.

A building has seven computers, numbered 0 to 6, and five cables, laid in this order: 0-1, 1-2, 3-4, 2-0 and 5-6.

  1. Start the parent array at 0 1 2 3 4 5 6 and process the cables in order, with no ranks and no path compression, writing the array after each.
  2. Count the separate networks from the final array.
  3. Name the redundant cable, and say how the trace revealed it.
  4. Say what the redundant cable is in a graph whose vertices are the computers and whose edges are the cables.
An answer: the trace, the count and the redundant cable

The trace shows the array after each cable. root-a marks the root whose parent changes and root-b the root it goes under; same-root marks the one cable whose ends already shared a root.

The parent array after each cable

InputComputers 0 to 6; cables 0-1, 1-2, 3-4, 2-0, 5-6, each setting the parent of one root to the other

  1. Start

    1. 0
    2. 1
    3. 2
    4. 3
    5. 4
    6. 5
    7. 6

    Seven computers and no cables yet: each computer is its own network and its own root.

  2. cable 0-1

    1. 1root-a
    2. 1root-b
    3. 2
    4. 3
    5. 4
    6. 5
    7. 6

    Roots 0 and 1 differ, so the parent of 0 becomes 1.

  3. cable 1-2

    1. 1
    2. 2root-a
    3. 2root-b
    4. 3
    5. 4
    6. 5
    7. 6

    find(1) is 1 and find(2) is 2, so the parent of 1 becomes 2.

  4. cable 3-4

    1. 1
    2. 2
    3. 2
    4. 4root-a
    5. 4root-b
    6. 5
    7. 6

    Roots 3 and 4 differ, so the parent of 3 becomes 4: a second network.

  5. cable 2-0

    1. 1
    2. 2
    3. 2same-root
    4. 4
    5. 4
    6. 5
    7. 6

    find(2) is 2 and find(0) climbs 0, 1, 2 to the same root, so this cable is redundant and nothing changes.

  6. cable 5-6

    1. 1
    2. 2
    3. 2
    4. 4
    5. 4
    6. 6root-a
    7. 6root-b

    Roots 5 and 6 differ, so the parent of 5 becomes 6: a third network.

ResultParent array 1 2 2 4 4 6 6: three roots, 2, 4 and 6, so three networks, and cable 2-0 was redundant

The final array is 1 2 2 4 4 6 6. Three cells hold their own index, 2, 4 and 6, so there are three networks: {0, 1, 2}, {3, 4} and {5, 6}. The run counted 3.

Cable 2-0 was redundant. find(2) returned 2 and find(0) climbed 0, 1, 2 to the same root, so 0 and 2 could already reach each other through 0-1 and 1-2, and the union changed nothing.

In the graph, that cable closes a cycle, 0 to 1 to 2 and back to 0. The same test therefore detects a cycle in any undirected graph: an edge whose two ends already share a root is an edge that closes one.

← → move through sections and cards