#include <fstream>
#include <iostream>
using namespace std;
enum Boolean { FALSE, TRUE };
class ListNode
{
friend void equivalence();
private:
int data;
ListNode* link;
ListNode(int);
};
typedef ListNode* ListNodePtr; //new를 사용하여 포인터 배열을 만들 수 있음
ListNode::ListNode(int n)
{
data = n;
link = 0; //linked list init
};
void equivalence()
{
ifstream fin("input.dat", ios::in); //입력파일 "input.dat"
if (!fin)
{
cerr << "Cannot open input file" << endl;
return;
}
int size;
fin >> size; //배열을 동적으로 잡기위해 동치쌍의 크기를 입력으로 줌
ListNodePtr* seq = new ListNodePtr[size];
Boolean* out = new Boolean[size];
for (int i = 0; i < size; i++) //배열의 초기화
{
seq[i] = 0;
out[i] = FALSE;
}
int x, y;
do
{
fin >> x >> y; //1단계 : 동치 쌍들을 입력 받는다.
ListNode* a = new ListNode(y); //seq[x]에 y를 첨가
a->link = seq[x];
seq[x] = a;
ListNode* b = new ListNode(x); //seq[y]에 x를 첨가
b->link = seq[y];
seq[y] = b;
} while (fin.good());
for (int i = 0; i < size; i++)
{
if (out[i] == FALSE)
{
cout << endl << "a new class: " << i;
out[i] = TRUE;
ListNode* a = seq[i];
ListNode* top = 0; //스택을 초기화
while (1) //부류의 나머지를 찾음
{
while (a)
{
x = a->data;
if (out[x] == FALSE)
{
cout << "," << x;
out[x] = TRUE;
ListNode* b = a->link;
a->link = top;
top = a;
a = b;
}
else a = a->link;
}
if (!top) break;
else
{
a = seq[top->data];
top = top->link; //스택에서 제거
}
}
}
}
delete[] seq;
delete[] out;
}
void main(void)
{
equivalence();
}
// 출력
* 출처 : https://blog.naver.com/shimchan2/70008915839 님의 블로그에서 퍼 옴
* 코드 이해 안 했음
* 동치 관계만 이해했음