What strategy should I follow to draw a forest of trees represented by an array

Question

I have an array of integers representing connectivity of nodes.Consider the following states of the array after each time it's changed:

0|1|2|3|4|5|6|7|8|9 => Root of each node is itself

0|1|2|3|3|5|6|7|8|9 => The root of 4 is 3

0|1|2|8|3|5|6|7|8|9 => The root of 3 is 8, so now 8 is root for 3 as well as 4.

And so on..

Each time two nodes get connected the array changes. I need to draw a tree representing the array state after each connection action. This is what I need to draw:

It's taken from Robert Sedgewick and Kevin Wayne's Algorithms book.

I've been banging my head against the wall but haven't been able to figure out what strategy I should take to solve this. Should I record the depth of the tree and draw level by level, or should I loop through the array one by one and draw the complete structure of each node with its children? I don't have a clue how to proceed with either way anyway. So I'd appreciate if someone could shed some light on this.

Answer 1

I think your conceptual difficulty is caused by the unstated implication that there is a second set of node 0-9. The array isn't the set of nodes.

Once you realise this the problem becomes simple

The root nodes are those where the array at index of the node Id is equal to the node id.

The children of any node are indicated by the indexes of the array which contain the node id, excluding the index which equals the node id.

ie

array = your input array
nodes = int[] {0,1,2....
roots = nodes.Where(i=> array[i] ==i)

getChildern(int node){
    return nodes.Where(i=> array[i] == node && i != node);
}

Answer 2

One way to approach it this:

1. Walk through the array one node at a time from the start
2. If a node refers to itself, draw it and mark it as drawn
3. If a node has a different parent, follow the chain to the root (keeping track of each node that you hit along the way
4. When you get to either the root or a node you've already drawn, draw the chain and mark each one in the chain as drawn.

Answer 3

You can try implementing something like DSU. Below is my implementation.

#include<iostream>
#include<vector>

using namespace std;

struct Node{
    int value;
    vector<Node*> childs;
};

/* I am doing a pre-order traversal Here. You can Traverse In any
 way(levelOrder will be best for verification) and verify that the tree constructed iscorrect. 
 */
void traverseOneTree(Node *tree){
    if(tree){
        cout<<tree->value<<" ";
        vector<Node*> child = tree -> childs;
        for(int i=0;i<child.size();i++)
            traverseOneTree(child[i]);
    }
}

void printAllTrees(vector<Node*> &trees){
    for(int i=0;i<trees.size();i++){
            // cout<<"i = "<<i<<trees[i]<<endl;
            traverseOneTree(trees[i]);
            cout<<endl;
    }
}

void join(vector<Node*> &trees,int child,int parent){
    if(trees[child] == NULL || trees[parent] == NULL)
            return; // invalid joining
    else{
        Node *newC = trees[child];
        trees[child] = NULL;
        trees[parent]->childs.push_back(newC);
    }
}

int main(){
    int nodes;
    cin>>nodes;
    vector<Node*> trees(nodes,NULL);
    for(int i=0;i<nodes;i++){
        trees[i] = new Node();
        trees[i]->value = i;
    }

    int joints;
    cin>>joints;
    while(joints--){
        int child,parent;
        cin>>parent>>child;
        join(trees,child,parent);
        printAllTrees(trees);
        cout<<"\n New Join\n";
    }

    return 0;

}