102644: [AtCoder]ABC264 E - Blackout 2
Description
Score : $500$ points
Problem Statement
A country has $N$ cities and $M$ power plants, which we collectively call places.
The places are numbered $1,2,\dots,N+M$, among which Places $1,2,\dots,N$ are the cities and Places $N+1,N+2,\dots,N+M$ are the power plants.
This country has $E$ power lines. Power Line $i$ ($1 \le i \le E$) connects Place $U_i$ and Place $V_i$ bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.
Now, $Q$ events will happen. In the $i$-th ($1 \le i \le Q$) event, Power Line $X_i$ breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.
Find the number of electrified cities right after each events.
Constraints
- All values in input are integers.
- $1 \le N,M$
- $N+M \le 2 \times 10^5$
- $1 \le Q \le E \le 5 \times 10^5$
- $1 \le U_i < V_i \le N+M$
- If $i \neq j$, then $U_i \neq U_j$ or $V_i \neq V_j$.
- $1 \le X_i \le E$
- $X_i$ are distinct.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $E$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_E$ $V_E$ $Q$ $X_1$ $X_2$ $\vdots$ $X_Q$
Output
Print $Q$ lines.
The $i$-th line should contain the number of electrified cities right after the $i$-th event.
Sample Input 1
5 5 10 2 3 4 10 5 10 6 9 2 9 4 8 1 7 3 6 8 10 1 8 6 3 5 8 10 2 7
Sample Output 1
4 4 2 2 2 1
Initially, all cities are electrified.
- The $1$-st event breaks Power Line $3$ that connects Point $5$ and Point $10$.
- Now City $5$ is no longer electrified, while $4$ cities remain electrified.
- The $2$-nd event breaks Power Line $5$ that connects Point $2$ and Point $9$.
- The $3$-rd event breaks Power Line $8$ that connects Point $3$ and Point $6$.
- Now Cities $2$ and $3$ are no longer electrified, while $2$ cities remain electrified.
- The $4$-th event breaks Power Line $10$ that connects Point $1$ and Point $8$.
- The $5$-th event breaks Power Line $2$ that connects Point $4$ and Point $10$.
- The $6$-th event breaks Power Line $7$ that connects Point $1$ and Point $7$.
- Now City $1$ is no longer electrified, while $1$ city remains electrified.
Input
题意翻译
### 题目描述 ZK 国有 $N$ 座城市和 $M$ 座发电站,我们称城市和发电站为地点。 这些地点的标号为 $1,2,\dots,N+M$,其中标号 $1,2,\dots,N$ 是城市,标号 $N+1,N+2,\dots,N+M$ 是发电站。 这个国家有 $E$ 条能源传输线路。第 $i$ 条线路双向连接地点 $U_i$ 和地点 $V_i$。一个城市如果可以通过某些线路到达发电站,则称这个城市是有供电的。 现在有 $Q$ 条询问。第 $i\;(1\le i\le Q)$ 条询问,代表第 $X_i$ 条线路停止工作,并且将来也无法修复。 每次询问后输出有供电的城市。 ### 输入描述 第一行三个整数 $N,M,E\;(N+M \le 2 \times 10^5)$。 接下来 $E$ 行每行两个整数 $U_i,V_i\;(1 \le U_i < V_i \le N+M,$ 且不会有两条线路连接相同的两个城市 $)$。 接下来一行一个整数 $Q\;(1 \le Q \le E \le 5 \times 10^5)$。紧跟着 $Q$ 行代表询问 $X_i\;(1\le X_i\le E)$。保证 $X_i$ 互不相同。 ### 输出描述 对于每组数据,输出一行一个数,第 $i$ 行代表对应询问的有供电的城市数量。 ### 样例 #1 ##### 样例输入 #1 ``` 5 5 10 2 3 4 10 5 10 6 9 2 9 4 8 1 7 3 6 8 10 1 8 6 3 5 8 10 2 7 ``` ##### 样例输出 #1 ``` 4 4 2 2 2 1 ```Output
问题描述
一个国家有N个城市和M个发电厂,我们统称这些地方为地点。
这些地方编号为1,2,\dots,N+M,其中地点1,2,\dots,N为城市,地点N+1,N+2,\dots,N+M为发电厂。
这个国家有E条电力线。电力线i(1 \le i \le E)双向连接地点U_i和地点V_i。
如果可以从城市通过一些电力线到达至少一个发电厂,那么该城市被认为是通电的。
现在,将发生Q个事件。在第i(1 \le i \le Q)个事件中,电力线X_i断裂,使其无法使用。一旦电力线断裂,它将在后续事件中保持断裂状态。
在每个事件之后立即找出通电的城市数量。
约束条件
- 输入中的所有值都是整数。
- 1 \le N,M
- N+M \le 2 \times 10^5
- 1 \le Q \le E \le 5 \times 10^5
- 1 \le U_i < V_i \le N+M
- 如果i \neq j,则U_i \neq U_j或V_i \neq V_j。
- 1 \le X_i \le E
- X_i是不同的。
输入
输入通过标准输入以以下格式给出:
$N$ $M$ $E$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_E$ $V_E$ $Q$ $X_1$ $X_2$ $\vdots$ $X_Q$
输出
打印Q行。
第i行应该包含第i个事件之后立即通电的城市数量。
样例输入1
5 5 10 2 3 4 10 5 10 6 9 2 9 4 8 1 7 3 6 8 10 1 8 6 3 5 8 10 2 7
样例输出1
4 4 2 2 2 1
最初,所有城市都是通电的。
- 第1个事件断裂连接地点5和地点10的电力线3。
- 第2个事件断裂连接地点2和地点9的电力线5。
- 第3个事件断裂连接地点3和地点6的电力线8。
- 第4个事件断裂连接地点1和地点8的电力线10。
- 第5个事件断裂连接地点4和地点10的电力线2。
- 第6个事件断裂连接地点1和地点7的电力线7。