/*
DisjointSets, 집합
수정날짜:9/8
*/
#include <iostream>
using namespace std;
class Sets
{
private:
int *parent;
int n; //집합의 요소 수
public:
Sets(int size = 10)
{
n = size;
parent = new int[size + 1]; //[0]은 사용하지 않는다
for (int i = 1; i <= n; i++)
parent[i] = -1; //최종부모를 -1로 둔다
}
~Sets()
{
delete[]parent;
}
bool operator==(Sets const &s1)
{
if (n != s1.n)
return false;
for (int i = 1; i <= n; i++) //하나라도 틀리면
if (parent[i] != s1.parent[i])
return false;
return true;
}
void SimpleUnion(int i, int j)
{
parent[i] = j; //i와 j가 다른 집합일 때 i 집합의 부모집합을 j집합으로 둔다
}
int SimpleFind(int i) //최종부모를 찾는다
{
while (parent[i] > 0)
i = parent[i];
return i;
}
void WeightedUnion(int i, int j) //SimpleUnion의 업그레이드 버전
{
int temp = parent[i] + parent[j];
if (parent[i] > parent[j]) //i가 더 적은 노드를 갖고 있을 때(음수이므로 이렇게 계산)
{
parent[i] = j;
parent[j] = temp;
}
else
{
parent[j] = i;
parent[j] = temp;
}
}
int CollapsingFind(int i) //i를 포함하는 집합의 루트를 찾는다(SimpleFind의 업그레이드 버전)
{
int r;
int count = 0;
for (r = i; parent[r] > 0; r = parent[r])
{
cout << "작동" << endl;//root를 찾는다
count++;
}
while (i != r)
{
int s = parent[i];
parent[i] = r;
i = s;
}
return r;
}
friend ostream &operator<<(ostream &os, Sets &s);
};
ostream &operator<<(ostream &os, Sets &s)
{
os << "첫번째 줄: 집합요소\t두번째 줄:부모(-1이면 root 혹은 최종부모)" << endl;
for (int i = 1; i <= s.n; i++)
os << i << "\t";
os << endl;
for (int i = 1; i <= s.n; i++)
{
os << s.parent[i] << "\t";
}
os << endl;
return os;
}
int main(void)
{
Sets s, t;
if (s == t)
cout << "두 집합은 동일합니다" << endl;
else
cout << "두 집합은 동일하지 않습니다" << endl;
cout << endl << "디폴트 집합 출력" << endl;
cout << s << endl;
cout << "2n이 2n-1의 부모가 되도록 설정" << endl;
for (int i = 1; i <= 5; i++)
s.SimpleUnion((2 * i - 1), 2 * i);
cout << s << endl;
cout << "10이 있는가? ";
cout << s.CollapsingFind(10) << endl;
cout << endl << "3n이 3n-1의 부모가 되도록 설정" << endl;
for (int i = 1; i <= 3; i++)
s.SimpleUnion((3 * i - 1), 3 * i);
cout << s << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.