POJ2524(Ubiquitous Religions)--并查集

题目链接：http://poj.org/problem?id=2524

学校有n个学生，但是你不能直接问学生的信仰，不然他会感到很不舒服的.一个方法是问m对同学，是否信仰同一宗教。根据这些数据,

计算学校最多有多少种宗教信仰的。 思路：使用并查集，一开始假设大家都各自信仰一个宗教，那么总的数目ans就是学生数目， 当发现有一对学生信仰同一个宗教，那么ans减1。 
  1 #include
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include
  8 #include<set>
  9 #include
 10 #include
 11 #include<string>
 12 #include
 13 #include
 14 using namespace std;
 15 
 16 
 17 struct node
 18 {
 19     /* data */
 20     int date;//结点对应的下标
 21     int parent;//双亲结点
 22     int rank;//结点对应秩（并查集树的深度）
 23     int relation; //与父节点的关系
 24     int total;
 25 };
 26 
 27 class DisJoinSet
 28 {
 29 protected:
 30     int n;//元素个数
 31     node *tree;//并查集元素数组
 32 public:
 33     int ans;
 34     DisJoinSet(int n );
 35     ~DisJoinSet();
 36     void Init();
 37     int Find(int x);// 查找x的代表元素（根），查找的同时进行路径压缩
 38     void Union(int x,int y);
 39     int GetAnswer();// 合并x和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++)//顶点编号 0～n-1  或  1 ～ n都 行 
 53     {
 54         tree[i].parent = i;//双亲初始化指向自已
 55         tree[i].rank = 0;//秩初始化为0
 56         tree[i].date = i;//编号
 57         tree[i].relation = 0;    //i自己是一类，它的父节点此时就是它自己，属于同一类
 58     }
 59 }
 60 
 61 DisJoinSet::~DisJoinSet()
 62 {
 63     delete []tree;
 64 }
 65 
 66 int DisJoinSet::Find(int x)//查找x的代表元素（根），查找的同时进行路径压缩
 67 {
 68     int temp = tree[x].parent;// 将x父节点的下标存入temp
 69     if( x != tree[x].parent)//若双亲不是自已
 70     {
 71         tree[x].parent = Find(tree[x].parent);//递归在双亲中找x
 72         return tree[x].parent;// 返回根节点下标
 73     }
 74     return x;//若双亲是自已,返回x
 75 }
 76 
 77 void DisJoinSet::Union(int x,int y)
 78 {
 79     int rootx = Find(x);// 找到下标为x的元素的根节点下标rootx
 80     int rooty = Find(y);// 找到下标为y的元素的根节点下标rooty
 81     if(rootx == rooty)// 已合并，直接返回
 82     {
 83         return ;
 84     }
 85     else
 86     {
 87         if(tree[rootx].rank > tree[rooty].rank)//rooty结点的秩（深度）小于rootx结点的秩
 88         {
 89             tree[rooty].parent = rootx;//将rooty连到rootx结点上,rootx作为rooty的孩子结点
 90             ans--;//合并两个人，总人数-1
 91             tree[rootx].total +=tree[rooty].total;
 92         }
 93         else
 94         {
 95             tree[rootx].parent = rooty;
 96             ans--;//合并两个人，总人数-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 "<": "<endl;
121     }
122     return 0;
123 }
数据结构树形结构-幷查集并查集算法poj

相关

数据结构--栈（C语言实现）

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

牛客练习赛91（并查集+二维偏序+二分）

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

标签