Mock CCO '19 Contest 2 Problem 1 - A Dynamic Connectivity Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 0.6s

Java 8 1.0s

Memory limit: 162M

Problem type

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

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

Constraints

$1 \le N \le 2M$ ~1 \le N \le 2M~

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

All vertices are labeled from $0$ ~0~ to $N-1$ ~N-1~.

Input Specification

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

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

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

$K$ ~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$ ~K+1~ lines. On line $i$ ~i~, output the number of connected components after the first $i-1$ ~i-1~ vertices have been deleted.

Sample Input

Sample Output

Comments

4

Swarley commented on May 13, 2019, 2:37 p.m. ← edit 2 →

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