Dynamic Equivalence Relation A dynamic equivalence relation is a data structure to keep track of things in the same class when you gradually discover that single items are of the same class. The formal requirements for the equivalence releation are: A eq A (reflexive) A eq B == B eq A (symmetric) A eq B and B eq C == A eq C (transitive) The term "dynamic" means that the releationship changes gradually as you find more information. This sounds a bit dry, bit it is really quite simple. Assume that you have a list of computers with network connections, and you want to find out which computers can reach each other. The term "reach" is the equivalence releation. Since a computer can always reach itself the releation is reflexive. Check. Assuming no unidirectional network links if computer A can send packets to B means computer B can send packets to A, so the releation is also symmetric. Check. Assuming that all computers can forward packets the if A can reach B and B can reach C then A can reach C, so the releation is transitive. Check. So you can use a Dynamic Equivalence Relation to find out which computers can reach each other. This implementation uses path compression and subtree balancing giving a time complexity of O(N lg lg N) This means that for 2^16 network links you can find which computers are connected in less that 262144 steps.