A Dynamic Connectivity Problem

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Java 8 1.0s
Memory limit: 162M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A graph has N vertices and M edges. When a vertex is deleted, all incident edges are deleted.

Given a sequence of K vertices to be deleted one by one, count the number of connected components before and after each deletion.


1 \le N \le 2M

1 \le M \le 2 \cdot 10^5

All vertices are labeled from 0 to N-1.

Input Specification

The first line contains two space-separated integers, N and M.

Each of the next M lines contains two space-separated integers, a_i and b_i, indicating that a_i and b_i are connected with an edge.

Next, a single integer K follows on its own line, indicating the number of vertices that will be deleted.

K lines follow, each indicating a vertex that is to be deleted. A vertex will be deleted at most once.

Output Specification

Output K+1 lines. On line i, output the number of connected components after the first i-1 vertices have been deleted.

Sample Input

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6

Sample Output



  • 1
    Swarley  commented on May 13, 2019, 10:37 a.m. edit 2

    what are the restrictions on k? EDIT: nevermind obviously k <= m