両親の木-等価類
両親の木の思想で等価類を実現しました.パス圧縮が完了しました.アルゴリズムは依然として厳しい蔚敏の教材の中の等価類の章節の中のアルゴリズムを採用しています.
/* Author : Moyiii
* Mail: [email protected]
* &
* ，
* ， 。
*/
#include<iostream>
using namespace std;
#define MAX_NODES 100
class PTree
{
public:
PTree();
void print();
void input();
int findClass(int a);
private:
void mergeNodes(int a,int b);
void fixNode(int a);
int nodes[MAX_NODES];
int nodeNum;
};
PTree :: PTree()
{
nodeNum = 0;
}
// ，
void PTree :: input()
{
cout << "Please enter the amount of the nodes:";
cin >> nodeNum;
for(int i = 0; i < nodeNum; ++i)
{
nodes[i] = -1;
}
cout << "Please enter two numbers that belong to the same class" << endl;
cout << "End with -1 -1" << endl;
int m,n;
while(cin >> m >> n && m != -1 && n != -1)
{
if(m > nodeNum || n > nodeNum)
{
cout << "Error data!" << endl;
continue;
}
//
int i = findClass(m);
int j = findClass(n);
mergeNodes(i,j);
}
}
//
int PTree :: findClass(int a)
{
fixNode(a);
while(nodes[a-1] > 0)
{
a = nodes[a - 1];
}
return a;
}
// a a a
void PTree :: fixNode(int a)
{
// a
int paren = a;
while(nodes[paren - 1] > 0)
{
paren = nodes[paren - 1];
}
int temp = a;
// a paren
while(nodes[temp - 1] > 0)
{
int x = nodes[temp - 1];
nodes[temp - 1] = paren;
temp = x;
}
return;
}
// ，
void PTree :: mergeNodes(int a, int b)
{
// ，
if(a == b)
{
return;
}
if(nodes[a - 1] < nodes[b - 1])
{
nodes[a - 1] += nodes[b - 1];
nodes[b - 1] = a;
fixNode(a);
}
else
{
nodes[b - 1] += nodes[a - 1];
nodes[a - 1] = b;
fixNode(b);
}
}
//
void PTree :: print()
{
cout << "----------Datas-----------" << endl;
for(int i = 0; i < nodeNum; ++i)
{
cout << i+1 << " " << nodes[i] << endl;
}
return;
}
/*
8
3 5
6 7
3 7
-1 -1
*/
int main()
{
PTree eq;
eq.input();
cout << eq.findClass(3) << endl;
eq.print();
return 0;
}