graph valid tree

Jyothi
2 min readApr 13, 2022

--

Problem statement

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Basically the expectation is that there should not be cycles in a graph and all nodes should be connected.

This solution can be implemented using BFS/DFS/Disjoint sets. I feel that disjoint sets is more opt as there is no extra memory of stack. Please give comments on it.

If we go with disjoint data structures, after connecting all the given edges, number of root elements equal to the number of disjoint sets.
Here the expectation is all nodes should be connected means there should be only one root element.
So if the number of root elements are more than one, it should be returned as invalid graph tree.
While connecting a given edge, check if already connected. If the given two vertices are already connected, it should be returned as invalid graph tree.

While implementing union function of disjoint data structure, additional check has to be added to return as invalid graph tree if the given 2 edges already connected.
After forming the disjoint set, check the number of root nodes. If the number of root nodes more than 0, return as invalid graph tree.

Below is solution:

int find(int *rt, int x){
int rx = rt[x];
if (rx == x){
return x;
}
return (rt[x]= find(rt, rx));
}

int unin_link(int *rt, int *rnk, int x, int y){
int rx = find(rt, x);
int ry = find(rt, y);

/* return 0 if the link already exists */
if ((ry == x) || (ry == rx))
return 0;
/* link those x, y if rx and ry not same */
if (rx != ry){
/* if rnk[rx] is greater than rnk[ry], assign root[ry] = rx and return */
if (rnk[rx] > rnk[ry])
rt[ry] = rx;
else if (rnk[ry] > rnk[rx])
rt[rx] = ry;
else /* if both ranks same, assign one as parent and increment the other's rank */{
rt[ry] = rx;
rnk[rx] +=1;
}
}
return 1;
}

--

--

No responses yet