Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

How to solve this problem of connectivity on graph?

Revision en1, by 0x0002, 2023-09-29 16:53:50

I want to solve a problem, which includes three operations: add an edge, delete an edge, and check if the undirected graph is connected. Both online or offline algorithm is ok. How to solve it for $$$n,m \le 10^5$$$？($$$n$$$ denotes the number of vertexs, $$$m$$$ denotes the number of operations.）

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 0x0002 2023-09-29 16:54:11 2 Tiny change: ' \le 10^5$？($n$ denot' -> ' \le 10^5$?($n$ denot'
en1 English 0x0002 2023-09-29 16:53:50 337 Initial revision (published)