IITM2012

Question

1. What is equivalence relation? 2. How can u represent equivalence. relation with a data structure? 3. Which data structure? how efficient? How can u test for. equivalence efficiently?

Comments

no answer :O

Answer 1

Can't we use directed graphs for representing equivalence relations?

Comments

In a graph representation each element of the set will be a vertex and each equivalent class correspond to a strongly connected component rt?

Usually for interviews questions go like this - they tell us answer and take our feedback too :)

---

Again, to make it clear,

1. If we are already given that the input relation is equivalence relation, then the strongly connected component would give the correct partition.. we can find using DFS numbering method - i think it has complexity O(V+E) for adjacency lists, and O(V²) for adjacency matrix, in any case less efficient than the disjoint set DS.

2. but for general case of a relation, this might not be true..
Strongly connected component need not necessarily imply partitions i think..

Take this graph for example..

---

yes, I meant the first case..