poj 2524 Ubiquitous Religions （STL与非STL的对比）

　　这不是一道难题，只是一个普通的，相当基础的MFSet问题。

　　这题的题解到处都有，所以我就只是大概说说做法：将编号按照关系分类，最后统计一共有子树。

　　我提供了两种代码，主要是为了说明STL消耗较多的内存和时间。下面的是用了set的，明显内存消耗更大：

　　下面是我的代码，只要调整STL的值就可以改变统计方法：

View Code

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstdlib"
 4 #include "cstring"
 5 #include "cmath"
 6 #include "cctype"
 7 #include "vector"
 8 #include "set"
 9 #include "map"
10 #include "string"
11 #include "algorithm"
12 #include "stack"
13 #include "utility"
14 #include "queue"
15 using namespace std;
16 
17 #define INF 0x7fffffff
18 #define reset(a) memset(a, 0, sizeof(a))
19 #define copy(a, b) memcpy(a, b, sizeof(b))
20 #define PI acos(-1)
21 #define FMAX (1E300)
22 #define MAX 1000000000
23 #define feq(a, b) (fabs((a)-(b))<1E-6)
24 #define flq(a, b) ((a)<(b)||feq(a, b))
25 #define MAXN 50005
26 
27 #define STL 1
28 
29 int f[MAXN], cnt[MAXN];
30 
31 void init_set(int n){
32     for (int i=0; i<=n; i++)
33         f[i]=i, cnt[i] = 1;
34 }
35 
36 int find_root(int p){
37     if (f[p]!=p)
38         f[p] = find_root(f[p]);
39     return f[p];
40 }
41 
42 void merge_set(int p, int q){
43     int a = find_root(p), b = find_root(q);
44     if (cnt[a] < cnt[b])
45         f[a] = b, cnt[b] += cnt[a];
46     else
47         f[b] = a, cnt[a] += cnt[b];
48 }
49 
50 void fix_set(int n){
51     for (int i=0; i<=n; i++)
52         f[i] = find_root(i);
53 }
54 
55 int main(){
56     int m, n, CASE=0;
57 
58     while (~scanf("%d%d", &n, &m) && (n || m)){
59         init_set(n);
60         while (m--){
61             int a, b;
62 
63             scanf("%d%d", &a, &b);
64             merge_set(a, b);
65         }
66 #if STL
67         set<int> s;
68         s.clear();
69         for (int i=1; i<=n; i++)
70             s.insert(find_root(i));
71         printf("Case %d: %d\n", ++CASE, s.size());
72 #else
73         bool vis[MAXN];
74         int ans=0;
75         reset(vis);
76         for (int i=1; i<=n; i++){
77             int t = find_root(i);
78             if (!vis[t])
79                 ans++;
80             vis[t]=true;
81         }
82         printf("Case %d: %d\n", ++CASE, ans);
83 #endif
84     }
85 
86     return 0;
87 }