[C++知识库]山东大学实验二，用C++实现并查集

并查集的原理很简单，我们直接看代码。

#include<iostream>
#include<string.h>
using namespace std;
struct equivNode
{
?? ?int equivClass;//等价类标识符
?? ?int size;//等价类的元素个数
?? ?int next;//类中指向下一个元素的指针
};
void initialize(int num, equivNode*Node)
{
?? ?for (int i = 1; i <= num; i++)
?? ?{
?? ??? ?Node[i].equivClass = i;
?? ??? ?Node[i].size = 1;
?? ??? ?Node[i].next = 0;
?? ?}
}
void swap(int &a, int &b)
{
?? ?int temp;
?? ?temp = a; a = b; b = temp;
}
void unite(int classA, int classB, int num, equivNode*Node)
{
?? ?if (Node[classA].equivClass > Node[classB].equivClass)
?? ?{
?? ??? ?swap(classA, classB);
?? ?}
?? ?if (Node[classA].equivClass != Node[classB].equivClass)
?? ?{
?? ??? ?Node[classB].equivClass = Node[classA].equivClass;
?? ??? ?Node[Node[classA].equivClass].size+=Node[classB].size;
?? ??? ?Node[classB].size=0;
?? ??? ?if (Node[classA].next==0)
?? ??? ?{
?? ??? ??? ?Node[classA].next = classB;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?int k = Node[classA].next;
?? ??? ??? ?for ( k;;)
?? ??? ??? ?{
?? ??? ??? ??? ?if (Node[k].next==0)break;
?? ??? ??? ??? ?k = Node[k].next;
?? ??? ??? ?}
?? ??? ??? ?Node[k].next = classB;
?? ??? ?}
?? ??? ?if (Node[classA].size == 1)
?? ??? ??? ?{
?? ??? ??? ?Node[classA].size--;
? ? ? ? ? ? }
?? ??? ?}
}
void display(equivNode*Node, int num)//输出这个并查集
{
?? ?cout << "Output" << endl;
?? ?for (int k=1; k <= num; k++)
?? ?{
?? ??? ?int a = Node[k].size;
?? ??? ?int b = k;
?? ??? ?int t = 1;//t用作记录输出的逗号
?? ? ? ?if (Node[b].size!= 0)
?? ??? ?{
?? ??? ??? ?for (int j=1; j <= a;t++,j++)
?? ??? ??? ?{
?? ??? ??? ??? ?if (j == 1)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?cout << "(";
?? ??? ??? ??? ?}
?? ??? ??? ??? ?cout << b;
?? ??? ??? ??? ?if (t < a)cout << ",";
?? ??? ??? ??? ?b = Node[b].next;
?? ??? ??? ??? ?if (j == a)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?cout << ")";
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?cout << endl;
? ? ? ? }
?? ?}
}
int main()
{
?? ?cout << "Input" << endl;
?? ?int num, rela;
?? ?char a,b,c,d,e;
?? ?cin >> num >> rela;
?? ?equivNode*Node=new equivNode[num+1];
?? ?initialize(num,Node);
?? ?int classA, classB;
?? ?for (int j = 1; j <= rela; j++)
?? ?{
?? ??? ?cin >> a >> b >> c >> d >> e;
?? ??? ?classA = (int)(b-48); classB = (int)(d-48);
?? ??? ?//cin >> classA >> classB;
?? ??? ?//cout << "完毕" << endl;
?? ??? ?unite(classA, classB, num,Node);
?? ?}
?? ?display(Node,num);
?? ?cout << "End";
?? ?return 0;
}