동치 알고리즘

#include <stdio.h>
#include <atlalloc.h>
#define MAX_SIZE 24
#define IS_FULL(ptr) (!(ptr))
#define FALSE 0
#define TRUE 1

struct node {
	int data;
	struct node* link;
};

int main(void) {
	short int out[MAX_SIZE];
	struct node* seq[MAX_SIZE], * x, * y, * top;
	int i, j, n;
	printf("Enter the size(<= %d) ", MAX_SIZE);
	scanf_s("%d", &n);

	//seq[] out[] 초기화
	for (i = 0; i < n; i++) {
		out[i] = TRUE;
		seq[i] = NULL;
	}


	//input the equivalnece pairs
	printf("Enter a pair of numbers(-1 -1 to quit):");
	scanf_s("%d %d", &i, &j);
	while (i >= 0) {//-1이 입력되면 종료하도록
		x = (struct node*)malloc(sizeof(struct node));
		x->data = j;
		x->link = seq[i];
		seq[i] = x;
		//j를 리스트i의 앞에 추가함

		x = (struct node*)malloc(sizeof(struct node));
		x->data = i;
		x->link = seq[j];
		seq[j] = x;
		//i를 리스트j의 앞에 추가함


		printf("Enter a pair of numbers (-1 -1 to quit):");
		scanf_s("%d %d", &i, &j);
	}

	for (i = 0; i < n; i++) {
		if (!out[i]) continue; //out은 플래그임
		printf("\n New class: %5d", i);
		out[i] = FALSE;
		x = seq[i]; top = NULL;
		for (;;) {
			while (x) {
				j = x->data;
				if (out[j]) {
					printf("%5d", j); out[j] = FALSE;
					y = x->link; x->link = top; top = x; x = y;
				}
				else x = x->link;
			}
			if (!top)
				break;
			x = seq[top->data]; top = top->link;
		}
	}
}

m: 입력된 동치항의 수, n: 원소의 수

전체적인 시간 복잡도 = O(m+n)