# Poj2524ubiquitous relationships

There are n students in the school, but you can't directly ask the students' beliefs, otherwise they will feel very uncomfortable. One way is to ask m to his classmates if they believe in the same religion. Based on these data,

Calculate the maximum number of religious beliefs in the school.
Idea: use and search the set. At the beginning, assume that everyone believes in a religion, then the total number is the number of students.
When it is found that a pair of students believe in the same religion, ans minus 1.
```  1 #include<iostream>
2 #include<stdio.h>
3 #include<cstring>
4 #include<cmath>
5 #include<vector>
6 #include<stack>
7 #include<map>
8 #include<set>
9 #include<list>
10 #include<queue>
11 #include<string>
12 #include<algorithm>
13 #include<iomanip>
14 using namespace std;
15
16
17 struct node
18 {
19     /* data */
20     int date;//Subscript corresponding to node
21     int parent;//Parent node
22     int rank;//Node corresponding rank (and look up the depth of set tree)
23     int relation; //Relationship with parent node
24     int total;
25 };
26
27 class DisJoinSet
28 {
29 protected:
30     int n;//Element number
31     node *tree;//Parallel set element array
32 public:
33     int ans;
34     DisJoinSet(int n );
35     ~DisJoinSet();
36     void Init();
37     int Find(int x);// lookup x Represents the element (root) of, and performs path compression while searching
38     void Union(int x,int y);
39     int GetAnswer();// merge x and y
40 };
41
42 DisJoinSet::DisJoinSet(int n)
43 {
44     this->n = n ;
45     tree = new node [n+1];
46     Init();
47     ans = n;
48 }
49
50 void DisJoinSet ::Init()
51 {
52     for(int i = 1 ;i <=n; i++)//Vertex number 0～n-1  Or 1 ～ n All right
53     {
54         tree[i].parent = i;//Parent initialization points to self
55         tree[i].rank = 0;//Rank initialized to 0
56         tree[i].date = i;//number
57         tree[i].relation = 0;    //i It belongs to the same category, and its parent node is itself at this time.
58     }
59 }
60
61 DisJoinSet::~DisJoinSet()
62 {
63     delete []tree;
64 }
65
66 int DisJoinSet::Find(int x)//lookup x Represents the element (root) of, and performs path compression while searching
67 {
68     int temp = tree[x].parent;// take x Subscript saving of parent node temp
69     if( x != tree[x].parent)//If parents are not themselves
70     {
71         tree[x].parent = Find(tree[x].parent);//Recursion in parents x
72         return tree[x].parent;// Return root node subscript
73     }
74     return x;//If parents are themselves,Return x
75 }
76
77 void DisJoinSet::Union(int x,int y)
78 {
79     int rootx = Find(x);// Found subscript as x The root node subscript of the element of rootx
80     int rooty = Find(y);// Found subscript as y The root node subscript of the element of rooty
81     if(rootx == rooty)// Merged, return directly
82     {
83         return ;
84     }
85     else
86     {
87         if(tree[rootx].rank > tree[rooty].rank)//rooty The rank (depth) of nodes is less than rootx Rank of nodes
88         {
89             tree[rooty].parent = rootx;//take rooty Connect to rootx Node,rootx Act as rooty Child node of
90             ans--;//Merge two people, total-1
91             tree[rootx].total +=tree[rooty].total;
92         }
93         else
94         {
95             tree[rootx].parent = rooty;
96             ans--;//Merge two people, total-1
97             tree[rooty].total += tree[rootx].total;
98             if(tree[rootx].rank == tree[rooty].rank)
99             {
100                 tree[rooty].rank++;
101             }
102         }
103     }
104 }
105
106 int main()
107 {
108     int n;
109     int m;
110     int t = 1;
111     while(cin>>n>>m && n !=0 &&m != 0)
112     {
113         DisJoinSet dis(n);
114         int a,b;
115         for(int i = 1 ;i <= m; i++)
116         {
117             cin>>a>>b;
118             dis.Union(a,b);
119         }
120         cout<<"Case "<<t++<<": "<<dis.ans<<endl;
121     }
122     return 0;
123 }```

Tags: PHP less

Posted on Sat, 02 Nov 2019 22:54:52 -0700 by mahers