Idea for Disconnected Graph

Revision en2, by dfsof, 2023-09-15 10:49:17

Hello lady/bros, I am struggling with 100551E.Disconnected Graph.

I have considered: (1) Online fully dynamic graph connectivity. I copied a piece of code here: https://www.luogu.com.cn/problem/solution/P5247. I passed LuoguP5247 and SPOJDYNACON2, however I could not pass this problem;

SPOJ Code

Codeforces submission is similar, but it always gets TLE on test15:

Codeforces Disconnected Graph Submission

(2)Retractable DSU, however it seems that DSU only supports rolling back the add options, it cannot roll back delete operations...

Tags graph, tree, dynamic connectivity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English dfsof 2023-09-15 10:50:20 0 (published)
en4 English dfsof 2023-09-15 10:50:13 17
en3 English dfsof 2023-09-15 10:49:55 36 Tiny change: ' on test15:\n\n<spoi' -> ' on test15, due to a relatively large constant:\n\n<spoi'
en2 English dfsof 2023-09-15 10:49:17 37
en1 English dfsof 2023-09-15 10:48:24 19700 Initial revision (saved to drafts)