Tying Rope

题目描述

有 $N$ 根绳子，编号为 $1$ 到 $N$。每根绳子的一端被涂成红色，另一端被涂成蓝色。 你将执行 $M$ 次绑绳子的操作。在第 $i$ 次操作中，你将把绳子 $A_i$ 的标记为 $B_i$ 的一端与绳子 $C_i$ 的标记为 $D_i$ 的一端系在一起，其中 $R$ 表示红色，$B$ 表示蓝色。对于每根绳子，同一颜色的一端不会被多次系上。 在所有操作完成后，求形成环的连接绳子组的数量，以及不形成环的那部分的数量。 这里，若可以重新排列连接组 $\lbrace v_0, v_1, \ldots, v_{x-1} \rbrace$ 中元素的顺序，使得对于每个 $0 \leq i < x$，绳子 $v_i$ 与绳子 $v_{(i+1) \bmod x}$ 相连，则称该连接组形成一个环。

输入格式

输入采用标准输入，格式如下： $N$ $M$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_M$ $B_M$ $C_M$ $D_M$

输出格式

按顺序以空格分隔输出 $X$ 和 $Y$，其中 $X$ 是形成环的连接绳子组的数量，$Y$ 是不形成环的连接绳子组的数量。

5 3
3 R 5 B
5 R 3 B
4 R 2 B

1 2

7 0

0 7

7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B

2 1

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq M \leq 2 \times 10^5$ $1 \leq A_i, C_i \leq N$ $(A_i, B_i) \neq (A_j, B_j), (C_i, D_i) \neq (C_j, D_j)$ $(i \neq j)$ $(A_i, B_i) \neq (C_j, D_j)$ $N, M, A_i$, and $C_i$ are integers. $B_i$ is $R$ or $B$, and so is $D_i$.共有三组连接的绳子：$\lbrace 1 \rbrace$、$\lbrace 2,4 \rbrace$ 和 $\lbrace 3,5 \rbrace$。 绳子组 $\lbrace 3,5 \rbrace$ 形成一个环，而绳子组 $\lbrace 1 \rbrace$ 和 $\lbrace 2,4 \rbrace$ 则不形成环。因此，$X = 1$ 且 $Y = 2$.

标签: AtCoder|abc293D

来源

AtCoder|abc293D