#include <iostream>
#include <cstdio>
struct Set;
struct Node{
int value;
Node* next=nullptr;
Set* mS=nullptr;
Node(int _value, Set* _mS): value(_value), mS(_mS) {}
};
struct Set{
Node *head=nullptr, *tail=nullptr;
int sN;
Set(int _sN): sN(_sN){}
~Set(){}
void Insert(int value){
Node* nN=new Node(value, this);
if(head==nullptr) {
head=nN;
tail=nN;
}
else {
Node* cur=this->head;
while(cur->next!=nullptr) cur=cur->next;
cur->next=nN;
}
}
void Delete(int value){
if(head==nullptr){
perror("NO KEY VALUE");
exit(1);
}
Node* cur=this->head;
while(cur->next!=nullptr && cur->next->value!=value){
cur=cur->next;
}
if(cur->next!=nullptr){
Node* tmp=cur->next->next;
cur->next=tmp;
delete cur->next;
}
}
};
struct Sets{
static int sN;
Set** sets;
int maxSz=4, cap=0;
Sets(){
sets=new Set*[maxSz];
}
void MakeSet(int x){
if(this->maxSz==this->cap){
Set** newSets=new Set*[this->maxSz*2];
for(int i=0; i<this->cap; ++i) newSets[i]=sets[i];
delete[] sets;
sets=newSets;
maxSz*=2;
}
Set* nS=new Set(sN++);
nS->Insert(x);
sets[cap++]=nS;
}
Set* FindSet(int x){
for(int i=0; i<cap; ++i){
Set* curS=sets[i];
Node* curN=curS->head;
if(curN==nullptr) continue;
while(curN!=nullptr){
if(curN->value==x) return curS;
curN=curN->next;
}
}
return nullptr;
}
void Union(int x, int y){
Set* setX=FindSet(x);
Set* setY=FindSet(y);
if(setX==nullptr || setY==nullptr){
perror("NO KEY VALUE");
exit(1);
}
if(setX==setY) return;
for(int i=0; i<this->cap; ++i){
if(this->sets[i]==setY){
sets[i]=sets[cap-1];
sets[cap-1]=nullptr;
break;
}
}
Node* cur=setY->head;
do{
cur->mS=setX;
cur=cur->next;
}while(cur!=nullptr);
setX->tail->next=setY->head;
setX->tail=setY->tail;
cap--;
delete setY;
}
};
int Sets::sN=1;
int main(void){
Sets* sets=new Sets();
for(int i=1; i<11; ++i) sets->MakeSet(i);
int edge[7][2]={
{2, 4},
{5, 7},
{1, 3},
{8, 9},
{1, 2},
{5, 6},
{2, 3}
};
for(int i=0; i<7; ++i){
sets->Union(edge[i][0], edge[i][1]);
}
return 0;
}