#include<stdio.h>
#include<conio.h>
#include<windows.h>
#include<process.h>

#pragma warning(disable : 4996)

void main()
{
	// 와샬 알고리즘을 진행하기 위한 변수 및 이중 포인터 변수 정의
	int i, j, k, m, n, s, t, domain, ** Mrs;

	// 관계행렬의 크기를 사용자로부터 입력받음
	printf("\n 집합 A는 1부터 n까지의 자연수를 갖는다. 자연수 n을 입력하라. : ");
	scanf("%d", &domain);

	// 입력될 관계를 저장하기 위한 이중 포인터로 이루어진 2차원 배열의 할당 및 초기화
	Mrs = (int**)malloc(sizeof(int*) * domain);
	for (i = 0; i < domain; i++)
	{
		*(Mrs + i) = (int*)calloc(domain, sizeof(int));
	}
	// - 1 - 1이 입력될 때까지 사용자로부터 관계를 입력받으면서 Mrs에 대입
	printf("\n집합 A에 대한 관계들을 (멈추기 위해 -1 –1)을 입력하라.:\n");
	do
	{
		scanf("%d %d", &i, &j);
		if (i == -1)
		{
			break;
		}
		else
		{
			(*(*(Mrs + i - 1) + j - 1)) = 1;
		}
	} while (1);

	// 입력된 관계행렬을 출력
	printf("\n[ 관계행렬 ]\n");
	for (i = 0; i < domain; i++)
	{
		for (j = 0; j < domain; j++)
		{
			printf("%d ", *(*(Mrs + i) + j));
		}
		printf("\n");
	}
	printf("\n<<아무 키나 입력하라.>>");
	getch();
	printf("\n");
	// 해당 제일 바깥쪽 for 문으로 관계행렬(Mrs)을 계산해서 단계별로 출력 진행
	for (i = 0; i < domain; i++)
	{
		for (j = i + 1; j < i + domain; j++)
		{
			for (k = i + 1; k < i + domain; k++)
			{
				m = j % domain;
				n = k % domain;
				if (Mrs[i][n] == 1 && Mrs[m][i] == 1)
				{
					Mrs[m][n] = 1;
				}
			}
		}
		// 한 단계가 끝나면 수정된 관계행렬을 출력
		printf("     [W%d]     \n", i + 1);
		for (s = 0; s < domain; s++)
		{
			for (t = 0; t < domain; t++)
			{
				printf("%d ", *(*(Mrs + s) + t));
			}
			printf("\n");
		}
		printf("\n");
		// 한 단계가 끝난 후에 관계를 출력
		for (s = 0; s < domain; s++)
		{
			for (t = 0; t < domain; t++)
			{
				if (*(*(Mrs + s) + t) == 1)
				{
					printf("(%d, %d) ", s + 1, t + 1);
				}
			}
		}
		// 다시 진행하거나 for 문을 멈춤
		printf("\n<<아무 키나 입력하라.>>");
		getch();
		printf("\n\n");
	}
	// 할당된 메모리 공간을 해제
	for (i = 0; i < domain; i++)
	{
		free(*(Mrs + i));
	}
	free(Mrs);
	system("PAUSE");
}