Equivalence Class

4/26 Fri

Equivalence Class
B(1,2)과 B(2,1)은 같음
bridge의 connection을 생각할 수 있음

1. B(x,y) 거나

conenct되어 있다는 정의 -> 그룹핑이 가능하다 -> Equivalence Class

Equivalence Class가 어떻게 되어 있는지 그룹을 ?
Q1) 최대한 팀이 몇개 있는지 구하라

Equivalenc한 List를 생성 (일종의 bridge)

• 그룹 넘버 생성 -> 그룹에 속하지 않은 것 체크 -> 리스트 생성 ->0,4,11 체크 -> 7체크? 11 2 순으로 체크

equiv
0-4-11
1-3
2-11
3-1-5
4-0-7
5-3
6-10
7-4
8-9-6
9-8
10-6
11-2-0

class number 1
0-4-11-7-2
class number 2
1-3-5
class number 3
6-10-8-9

각 element(12개)에 관한 List 생성
주어진 pair의 개수 - 9개

equiv 한바퀴 돌면서 리스트 생성
equiv[a] 해당하는 곳에 b 입력

find_equiv_class()

a_class

intlist_len(a_class) // a_class 크기
n_checked++ 면 a_class의 크기가 커짐