Hi,
I'm currently working on UVa 1197: The Suspects. Taking the natural graph theory interpretation, the problem is asking us to find the number of vertices in the same connected component as vertex 0.
I have implemented two different ways to solve this problem. One of them gives me AC, and the other one gives me TLE. However, it seems like the the solution that is giving me TLE is more efficient than the solution that gives me AC.
Implementation #1 gives me AC, and it uses the union find data structure with path compression and union by rank. Essentially, I just create a union find data structure, and I union sets when they are in the same friend group. Finally, I have a for-loop which checks whether the representative in the set is the same representative of the set that contains vertex 0. You can see my full implementation here: https://repl.it/@kekesh/UVA-1197-with-Union-Find
Implementation #2 gives me TLE. It just constructs a graph, and it performs a depth-first search with vertex 0 as the source node. A full implementation is here: https://repl.it/@kekesh/UVA-1197-with-DFS
I know that the asymptotic complexity of operations in the union find data structure are described by the inverse Ackermann function; however, I remember reading in CLRS that depth-first search outperforms the union find data structure when the underlying graph is static (the edges and vertices do not change in the graph). It seems like the graph in this problem is static (we only find the connected components after the graph has been fully constructed), so I am confused as to why the DFS solution is giving me TLE.
I would appreciate it if someone could please help me explain why this is happening.
