Is there any algorithm that inserts a node in undirected graph iff graph is acyclic?

for example: if graph is like below

0 - 1
|
2 - 3
4 - 5

valid insertion : 2-4

0 - 1
|
2 - 3
|
4 - 5

invalid insertion : 1 - 3

0 - 1
|   |   <=== cyclic!!!
2 - 3
4 - 5

If there is any example code with c , I would really appreciate.

CodePudding user response：

You can maintain a disjoint-set data structure for the set of vertices. This structure has the following operations:

• find(x) to return the identifier of the set where x belongs,
• union(x,y) to merge the sets of x and y.

1. Start with a set for the each vertex.
2. Before adding an edge, check whether its ends are in the same set.
3. If not, add the edge and merge the corresponding sets.

For your example, the state of the data structure is the following:

• S1 = {0,1,2,3}
• S2 = {4,5}

When you try to add an edge 1-3, you get that vertices 1 and 3 belong to the same set S1, so you skip adding.

When you try to add an edge 2-4, you get that vertices 2 and 4 belong to the different sets (S1 and S2, correspondingly), you add this edge, and update the structure to be:

• S1 = {0,1,2,3,4,5}