入门OJ 4192： [Noip模拟题]黑魔法师之门 (并查集)

发表于 更新于 分类于

题目

Description

applepi被囚禁的地点只有一扇门，当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图，而打开这扇门的密码就是图中【每个点的度数大于零且都是偶数】的子图的个数对1000000009取模的值。此处子图 (V, E) 定义为：点集V和边集E都是原图的任意子集，其中E中的边的端点都在V中。但是Vani认为这样的密码过于简单，因此门上的图是动态的。起初图中只有N个顶点而没有边。Vani建造的门控系统共操作M次，每次往图中添加一条边。你必须在每次操作后都填写正确的密码，才能够打开黑魔法师的牢狱，去拯救伟大的领袖applepi。

Input

第一行包含两个整数N和M。

接下来M行，每行两个整数A和B，代表门控系统添加了一条无向边 (A, B)。

N≤200000，M≤300000 ## Output 输出一共M行，表示每次操作后的密码。 # 题解 一道海星的并查集

主要难度在理解题意上了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <vector>
using namespace std;
class UnionFind {
 private:
  int quantity;
  vector<int> union_;
 public:
  UnionFind(const int maximum = 1) {
    union_.assign(maximum + 10, 0);
    quantity = maximum;
    for (register int i(1); i <= maximum; ++i) {
      union_[i] = i;
    }
  }
  inline void Assign(const int &maximum) {
    union_.clear();
    union_.assign(maximum + 10, 0);
    quantity = maximum;
    for (register int i(1); i <= maximum; ++i) {
      union_[i] = i;
    }
  }
  inline int Find(const int &x) {
    return union_[x] == x ? x : union_[x] = Find(union_[x]);
  }
  inline void Merge(const int &u1, const int &u2) {
    const int tmp1(this->Find(u1)), tmp2(this->Find(u2));
    union_[tmp2] = tmp1, union_[u2] = tmp1;
  }
};
UnionFind unions;
const int kMod(1000000009);
int n, m, x, y, ans(1);
int main(int argc ,char **argv) {
  scanf("%d %d", &n, &m);
  unions.Assign(n);
  while (m--) {
    scanf("%d %d", &x, &y);
    if (unions.Find(x) != unions.Find(y))unions.Merge(x, y);
    else ans *= 2;
    if (ans > kMod) ans -= kMod;
    printf("%d\n", ans - 1);
  }
  return 0;
}