Блог пользователя hseke

Автор hseke, история, 5 лет назад, По-английски

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.

Thank you.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

You're passing vector<vector<int>> AdjList by value in dfs function, that's very slow. Either change it to passing by (const) reference, or make it a global variable.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Just changing void dfs(ll &size, ll curr, vector<vector<int>> AdjList) to void dfs(ll &size, ll curr, const vector<vector<int>>& AdjList) gave me AC in the second implementation. Thank you -- I didn't realize that this could make such a big difference.