分层并查集
P2024 [NOI2001] 食物链。
并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。
异或方程组
例题。
有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma a_i \oplus a_i \oplus 1$ 就可以计算边上有多少点和自己属于同一块。
得到异或方程组之后进行简单的高斯消元即可。
P2024 [NOI2001] 食物链。
并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。
例题。
有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma a_i \oplus a_i \oplus 1$ 就可以计算边上有多少点和自己属于同一块。
得到异或方程组之后进行简单的高斯消元即可。