[Solved] A program which is difficult


Essentially, your question is this:
given a graph with nodes represented as indices and edges as index pairs,
and given an index i that represents a node,
find all nodes which are connected to the given node.

UnionFind algorithm to find connected components over nodes with indices:

Initialize an array father of size number of nodes, with father[i] = i

for each edge e consisting of two indices i, j:
    ind = i
    while(ind != father[ind]) ind = father[ind]
    father[j] = ind

for each entry i of the array:
    replace father[i] by father[father[i]] until those are equal

After that, all nodes in the same component have the same father. You do that with your data, and then, for a given index i, find all other indices j with father[i] = father[j].

(slight improvement in run time: after ind is set to it’s final value, update the father of i and its father and so on to the value ind)

Short explanation of UnionFind: it creates a tree in which only index pointers to the father of a node is stored (requires only an array). This is done by iterating over the edges. For every edge, the father of one of the incident nodes is set to the highest ancestor of the other node. Essentially, we start with a forest of single nodes and assemble them to trees. At the end, we change the remaining trees so that all leaves are direct children of the root.

Since in your example some numbers are missing, you might want to create some table that translates your input index to a range of numbers which are actually used. However, if we are talking about a small maximum index, like under one thousand, it won’t really hurt not to do it.

solved A program which is difficult