CareerCup

@hprem991 -> i am not sure this would work. Consider the following graph with nodes (A,B,C,D) where
A->B->D and A->C->D

On the first visit to 'D', you will have a union between A and D. on a second visit (via C) you will falsely conclude that you have a cycle.

Yes you can.. It is same as using normal cycle detection with set concept.

Algo,

For each node in a graph {
if(Find(parent, parent->child[index])){
Cycle detected
} else {
Union(Set, parent, parent->child[index])
}
}

Hprem991 how about the following graph.?
A->B->C A->D ->C? You will union C to A only to find it again through D. Yet it is acyclical.

i don't think the original union-find can solve this, because it's based on finding "the common parent", which cannot form a cycle in a directed graph.

both functions wouldn't work.
1) find_parent: a node might have multiple parents.
2) union: it doesn't make sense to combine two paths (with potential opposite directions) as one.

Its not possible to use Union Find for directed graph because Union Find works on Disjointed Sets only and relies heavily on set properties like contains/find and join. Sets by definition dont have any order i.e. if set contains vertices A, B then there will be no way to differentiate if a-> b or b -> a thus we can only use set to to have undirected edges. In other words a direction in a edge denotes and order and sets bu definition are orderless