[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 4.8 동치 관계 연습문제

#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 님의 블로그에서 퍼 옴

* 코드 이해 안 했음

* 동치 관계만 이해했음