A fraud-detection service merges accounts into groups as evidence links them, and needs to answer "are these two accounts the same person?" many times a second as new evidence arrives continuously. Someone suggests running a graph traversal (BFS/DFS) on every query. What's the better structure, why, and what's the actual complexity guarantee it gives you?

Union-find is the right structure specifically because this is the shape it's built for: groups merge over time as evidence arrives, and membership is queried repeatedly as it does. A fresh BFS or DFS answers one connectivity question in O(V+E), and paying that cost on every single query — when evidence keeps arriving continuously — means re-paying the whole traversal cost every time, whereas union-find answers each query in effectively constant time after the merges that produced the current groupings. The naive implementation (every element points at a parent, follow parents to find the group's representative) has one flaw: without care, the chains it builds can degenerate into a long line, making a single query O(n). The fix is path compression — every time you follow a chain to find the representative, you flatten the path you just walked so every future query on those same elements is short — measured in this course at three thousand times faster for a worst-case chain. Combined with a second optimisation (union by rank), the proven amortised cost per operation is O(α(n)), the inverse Ackermann function, which is below 5 for any number of elements that could physically exist — genuinely, provably "effectively constant", not an approximation.