• Relation의 정의
• 집합 A에 대하여, AxA의 부분집합을 A에 대한 relation이라 한다.
• ex1) A = {1, 2, 3}일 때, AxA = {(1, 1), (1, 2), (1, 3), (2, 1), ..., (3, 3)}
• R = {(1, 3), (1, 1), (2, 2)} 는 A의 relation이라 할 수 있다.
• 이때, (1, 3) ∈R 을 1R3으로 표기한다.
• ex2) 부등호 <를 N(자연수 집합)의 relation으로써 정의할 수 있다.
• < = {(1, 2), (1, 3), ..., (2, 3), (2, 4), ...}
• 2<4는 (2, 4)∈< 를 의미하게 된다.

• 다음 세 가지를 만족하는 A의 relation R은 equivalence relation이라 한다.

• R로부터 유도되는 Partition A₁, A₂, A₃, ...이란?
• Partition은 아래 조건을 만족하는 모든 A_i의 집합을 의미한다.
• 만약 a∈A_i 이면, aRb일때  b∈A_i 를 만족해야 한다.
• 단, A_i는 공집합이 아니다.

• 직관적으로 말하면, 사람의 눈 색이 검은색, 갈색, 파란색 뿐이라고 가정한 경우, 사람들을 눈 색이 검은색, 갈색, 파란색인 세 개의 집합으로 나눈 것이다.

• P = {A₁, A₂, A₃}
• A₁ = {6, 2}, A₂ = {1, 3, 9, 7, 4}, A₃ = {5, 10, 8}

1. A의 원소들의 값의 범위가 1~N 일 때, NxN 2차원 배열 M과 길이 N의 1차원 배열 L을 생성한다. 두 배열의 원소들은 0으로 초기화되어 있다. DFS에서 배열 M의 각 행을 방문할 것이다.
2. 동치 관계의 순서쌍이 입력될 때마다, 2차원에서 해당 순서쌍에 대응하는 위치의 값을 1로 바꾼다. 배열의 값은 다음과 같이 바뀐다.
• 
• (N=10 인 경우)
3. 배열 L에서 값이 0인 인덱스를 하나 찾아 변수 i에 대입한다.
• 변수 i는 현재 방문하고 있는 배열 M의 행 인덱스를 나타낸다.
4. i를 출력하고, L[i]를 1로 바꾼 뒤 M[i][1]에서 시작하여 값이 1인 칸을 찾을 때까지 M[i][N] 으로 직선 방향으로 이동한다.
• 
  
5. 값이 1인 칸을 찾았고, 해당 칸의 열 인덱스가 k라 하자. 
• 
  
• L[k]가 0면 L[k]의 값을 1로 고치고 i를 stack에 push한다. 그 다음 i의 값을 k로 고치고 i를 출력한다.
• 
  
• L[k]가 1이면 해당 칸을 무시하고, M[i][N] 까지 이동하는 것을 반복한다.
6. M[i][N] 까지 이동을 마쳤다면, stack에서 pop한다. pop한 값이 k라면, M[k][i]로 이동하고, i를 k로 고치고, 이동을 다시 시작한다.
• 
  
• M[3][7]에서 M[7][1]로 이동한 뒤, 7행의 끝까지 이동했다고 하자. 다시 3행으로 돌아오는 경우, M[3][8]부터 보면 된다. 
7. M[i][N]까지 이동을 마쳤는데도 stack에 남아 있는 값이 없다면, 줄바꿈을 출력한 뒤 3번 과정부터 다시 시작한다. L의 모든 값이 1이라면 알고리즘을 마친다.

1 3 7 9 4
2 6
5 10 8

1. 배열 L에서 걸리는 시간
• 각 DFS를 시작할 때, 배열 L의 처음부터 본다면 O(N²) 시간이 걸린다.
• 배열 L을 어디까지 봤는지를 다른 변수에 기록한다면, 처음부터 시작할 필요가 없다. 이 경우 O(N)이 걸린다.
2. Stack에서 걸리는 시간
• stack에서의 push, pop연산은 M에 있는 1개수를 초과하여 수행될 수 없다.
• 입력값에서 유추가 가능한 쌍은 주어지지 않으므로, 입력값 쌍 개수는 N개 이하여야 하고, 1의 개수는 2N개 이하가 된다.
• 따라서 stack에서는 O(N) 시간이 걸린다.
3. M에서 걸리는 시간
• 각 행을 보는 데 O(N)시간이 걸린다. 행을 반복해서 보지 않고, 행의 개수는 N개이므로, 총 O(N²)시간이 걸린다.