首页 > 代码库 > Codeforces Round #254 (Div. 2) DZY Loves Chemistry【并查集基础】

Codeforces Round #254 (Div. 2) DZY Loves Chemistry【并查集基础】

一开始不知道题意是啥意思,迟放进去反应和后放进去反应有什么区别

对于第三组数据不是很懂,为啥312,132的组合是不行的

 

后来发现这是一道考察并查集的题目 QAQ

怒贴代码:

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <iostream> 6 #include <algorithm> 7 using namespace std; 8  9 const int INF = 0x3f3f3f3f;10 11 int n, m, fa[100], x, y;12 13 int gf(int x) {14     if (fa[x] != x)    fa[x] = gf(fa[x]);15     return fa[x];16 }17 18 int main() {19     scanf("%d%d", &n, &m);20     for (int i = 1; i <= n; i++)    fa[i] = i;21     while (m--) {22         scanf("%d%d", &x, &y);23         fa[gf(x)] = gf(y);24     }25     long long ans = (1LL << n);26     for (int i = 1; i <= n; i++)27         if (gf(i) == i)    ans /= 2;28     printf("%I64d\n", ans);29 }