AHSOFNU NOIP模拟题-13 T1(并查集)

发表于 | 分类于 | | + s

可以观察样例发现规律，对于每一条加进来的边$(u, v)$，如果$u, v$连通，则$ans = ans \times 2 -1(ans = 1 when init)$，不连通就连边即可，显然用并查集维护。

有一个易懂的证明：
题目中每个点的度数大于零且都是偶数的子图等于这个子图就是几个环(它们之间不一定连通)，对于每一条加进来的边$(u, v)$，如果$u, v$连通，那么$(u, v)$连上以后会形成一个环。而如果有一条路径$L$连接$u,v$，那么可以用边$(u, v)$替换掉$L$，则之前的每个方案都可以替换，那么答案自然就多一倍了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "magician"
using namespace std;
const int MAXN = 200000 + 5, MO = 1000000009;
int n, m, fa[MAXN];
int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int find(int x) {return (fa[x] == x) ? (x) : (fa[x] = find(fa[x]));}
void clean() {
    for (int i=1;i<=n;i++) fa[i] = i;
}
void solve() {
    clean();
    int ans = 1;
    for (int i=1;i<=m;i++) {
        int a = read(), b = read();
        int x = find(a), y = find(b);
        if (x != y) fa[x] = y; else ans = (ans * 2) % MO; 
        printf("%d\n", ans - 1);
    }
}
int main() {
    freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
    n = read(), m = read(), solve();
    fclose(stdin); fclose(stdout);
    return 0;
}

黑魔法师之门
(magician.pas/c/cpp)
题目描述
经过了 16 个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与 Violet
星球的战争中，由于 Z 副官的愚蠢，地球的领袖 applepi 被邪恶的黑魔法师 Vani 囚禁在了
Violet 星球。为了重启 Nescafé这一宏伟的科技工程，人类派出了一支由 XLk、 Poet_shy 和
lydrainbowcat 三人组成的精英队伍，穿越时空隧道，去往 Violet 星球拯救领袖 applepi。
applepi 被囚禁的地点只有一扇门，当地人称它为“黑魔法师之门”。这扇门上画着一张
无向无权图，而打开这扇门的密码就是图中每个点的度数大于零且都是偶数的子图的个数
对 1000000009 取模的值。此处子图 (V, E) 定义为：点集 V 和边集 E 都是原图的任意子集，
其中 E 中的边的端点都在 V 中。
但是 Vani 认为这样的密码过于简单，因此门上的图是动态的。起初图中只有 N 个顶点
而没有边。 Vani 建造的门控系统共操作 M 次，每次往图中添加一条边。你必须在每次操作
后都填写正确的密码，才能够打开黑魔法师的牢狱，去拯救伟大的领袖 applepi。
输入格式
第一行包含两个整数 N 和 M。
接下来 M 行，每行两个整数 A 和 B，代表门控系统添加了一条无向边 (A, B)。
输出格式
输出一共 M 行，表示每次操作后的密码。
样例输入
4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3
样例输出
0 0 13 7 7
15
31
样例说明
第三次添加之后，存在一个满足条件的子图 {1, 2, 3}（其中 1, 2, 3 是数据中边的标号）。
第四次添加之后，存在三个子图 {1, 2, 3}， {1, 2, 4}， {3, 4}。
„„
数据范围与约定
对于 30% 的数据， N, M≤10。
对于 100% 的数据， N≤200000， M≤300000。

------ 本文结束 ------