POJ1611(The Suspects)--简单并查集

佚名 5年前 (2019-07-27) 算法 2068人围观抢沙发百度已收录

关于SARS病毒传染的问题。在同一个组的学生是接触很近的，后面也会有新的同学的加入。其中有一位同学感染SARS，那么该组的所有同学得了SARS。要计算出有多少位学生感染SARS了。编号为0的同学是得了SARS的。直接用并查集解决水掉

  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 #define MAX 100
 16 
 17 struct node
 18 {
 19     int no;//编号
 20     int rank;
 21     int parent;
 22     int total;
 23 };
 24 
 25 class DisJoinSet
 26 {
 27     protected:
 28         int n;
 29         node * tree;
 30     public:
 31         DisJoinSet(int n );
 32         ~DisJoinSet();
 33         void Init();
 34         void Union(int x,int y);
 35         int Find(int x);
 36         int GetAswer(int x);
 37 };
 38 
 39 DisJoinSet ::DisJoinSet(int  n)//初始化操作
 40 {
 41     this->n = n;
 42     tree = new node[n];
 43     for(int i = 0 ; i < n; i++)
 44     {
 45         tree[i].no = i;
 46         tree[i].parent = i;
 47         tree[i].total = 1;
 48         tree[i].rank = 0;
 49     }
 50 }
 51 DisJoinSet::~DisJoinSet()
 52 {
 53     delete[] tree;
 54 }
 55 
 56 void DisJoinSet :: Init()
 57 {
 58 }
 59 int DisJoinSet::Find(int x)
 60 {
 61     int temp = tree[x].parent;//temp 为x的父亲结点
 62     if( x != tree[x].parent)
 63     {
 64         tree[x].parent = Find(tree[x].parent);//路径压缩
 65         return tree[x].parent;
 66     }
 67     else
 68     {
 69         return x;
 70     }
 71 }
 72 
 73 void DisJoinSet ::Union(int x,int y)
 74 {
 75     int rootx = Find(x);
 76     int rooty = Find(y);
 77     if(rootx == rooty)
 78     {
 79         return ;
 80     }
 81     else//并查集基本操作
 82     {
 83         if(tree[rootx].rank < tree[rooty].rank)
 84         {
 85             tree[rootx].parent = rooty;
 86             tree[rooty].total += tree[rootx].total;
 87         }
 88         else
 89         {
 90             tree[rooty].parent = rootx;
 91             tree[rootx].total += tree[rooty].total;
 92             if(tree[rootx].rank == tree[rooty].rank)
 93             {
 94                 tree[rootx].rank++;
 95             }
 96         }
 97     }
 98 }
 99 
100 int DisJoinSet::GetAswer(int x)//返回xtotal
101 {
102     int t = Find(x);
103     return tree[t].total;
104 }
105 
106 int main()
107 {
108     int n;
109     int m;
110     while(cin>>n>>m && n!=0 && m>= 0)
111     {
112         DisJoinSet dis(n);
113         int per1;
114         int per2;
115         for(int i = 0; i< m;i++)
116         {
117             int num = 0;
118             cin>>num;
119             cin>>per1;
120             for(int i = 1 ;i < num; i++)
121             {
122                 cin>>per2;
123                 dis.Union(per1,per2);
124             }
125         }
126         cout<<dis.GetAswer(0)<<endl;
127     }
128     return 0;
129 }