maintain an Adjacency matrix. Matrix state: for each element(row), mark as 1 for a column, if row-> column is reachable.
when inserting, at (a,b) check if (b,a) is '1', if yes.. then there is cycle. (don't insert, or report) else add ==> mark (a,b) =1 and do the below step for each col, (b,col_num) if its '1', then mark (a,col_num) to 1. (it can be easier if it an undirected graph.) start ======== 1000 0100 0010 0001 A->B 1100 0100 0010 0001 C->D 1100 0100 0011 0001 D->B 1100 0100 0011 0101 C->A 1100 0100 1111 0101 when adding B->c, (C,A) is '1', don't insert space is O(V^2) --> if bit vector is used.. its Log(V). insertion time = O(V) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/dOhnXq9XGfAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.