HOJ2033 Ubiquitous ReligionsAnalysis:This is clearly a problem we can solve using the data structure called
Union Set.In this kind of problems,we are usually given a set of elements with subsets of them sharing the same feature,and then we are supposed to find out either the number of distinct subsets or whether or not two or more given elements are in the same subset.We may as well use the data structure
Tree,assigning each elements as a node.However,it is plain to see that the only way we can know whether two nodes belong to the same tree is to see if their ancestors are the same.Obviously,this can take quite a while when the number of nodes is large,so we want to create a new way of solving this kind of problem with high efficiency.So here we go,the
Union Set.
To begin with,Union Set is basicly a series of sets with vertices of a graph as their elements.Within each set,the elements share the same feature,and there is an element acting as the root or representative of the set.So we can see that actually each set itself is a Tree.The core idea of this kind of data structure is that the only thing matters is whether or not two elements belong to the same set,i.e,we only care about whether or not two nodes belong to the same tree,in other words,have the same root.As a result,we can ignore the detail of the tree,or each set.So now I think our task is clear.What we need to do is merely to divide the given nodes into sets,assign each set a representative,and build a connection between each node and the representative of the set it belongs to.
In practice,we are often given a list of information about connections between two nodes.So how to implement the idea above?If the two nodes given do not belong to any set,then we can simply assign the father of one of them to the other,and thus create a new set.But what if one or both of them have been in a set?Well,this is the beauty of this whole thing.In this case,we build a connection between the roots of the two sets,thus
merging the two sets into one larger.Amazing,isn't it?But hold on,there are two problems here.First,how to find the root of the set a node belongs to?Well,initially,we make the father of each node itself.Whenever we merge two elements,the father of one of them will be changed.To find out the root,or the ancestor,of a given node,we only need to recursively find the father of the current node until the father of it is itself.Apparently,we can use some techniques here,to make the whole process much faster.In the process of searching for the ancestor of a node,we must visit every node on the path between the node and its ancestor.So we can modify all the nodes on the path,changing their father to the root node,and thus saving a lot of efforts afterwards,in case another one of the nodes on this path is encountered in the queries.So here we go,the first problem is solved!Then comes the second problem,which is how we can know which of the two sets we are trying to merge into one is larger in size.To solve this,we assign each node a rank.Initially,all ranks are zero.Whenever a node becomes the root of a set,the rank of it denotes the size of the set,in other words,the number of nodes in the set.So when we are merging two sets,we make the father of the root of the smaller set the root of the larger set.Alright,now everything is done!
In this problem specifically,we are required to find out how many distinct religions a set of students believe in.We are given a list of information,where two students numbered from 1 to n believe in the same religion.There are in total m pieces of information.We can use the
Union Set to solve this problem within minutes.
Code:
1 #include<iostream>
2 using namespace std;
3 struct Mer
4 {
5 int father,rank;
6 }f[50001];
7 void Built(int n)
8 {
9 for(int i=1;i<=n;i++)
10 {
11 f[i].father=i;
12 f[i].rank=1;
13 }
14 }
15 int Search(int i)
16 {
17 if(i!=f[i].father)
18 {
19 f[i].father=Search(f[i].father);
20 }
21 return f[i].father;
22 }
23 void Merge(int a,int b)
24 {
25 int i=Search(a),j=Search(b);
26 if(i==j) return;
27 else
28 {
29 if(f[i].rank>=f[j].rank)
30 {
31 f[j].father=i;
32 f[i].rank+=f[j].rank;
33 }
34 else if(f[i].rank<f[j].rank)
35 {
36 f[i].father=j;
37 f[j].rank+=f[i].rank;
38 }
39 }
40 }
41 int main()
42 {
43 int n,m,a,b,counter=0;
44 while(scanf("%d %d",&n,&m)==2)
45 {
46 if(!n && !m) break;
47 Built(n);
48 while(m--)
49 {
50 scanf("%d %d",&a,&b);
51 Merge(a,b);
52 }
53 int max=n;
54 for(int i=1;i<=n;i++)
55 {
56 int root=Search(i);
57 if(f[root].rank!=1)
58 {
59 max-=f[root].rank-1;
60 f[root].rank=1;
61 }
62 }//Find out the number of distinct sets
63 printf("Case %d: %d\n",++counter,max);
64 }
65 return 0;
66 }
67
This problem,in my opinion,is a typical one about the
Union Set.