Poj2524ubiquitous relationships

Title Link: http://poj.org/problem?id=2524

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