문제

• 요약

1. 사람의 수 N과 파티의 수 M이 주어짐
2. 진실을 아는 사람의 수와 번호가 주어짐
3. M개의 줄에 각 파티마다 오는 사람의 수와 번호가 주어짐

풀이

1. 유니온 파인드 생각

• 뒤에 입력되어도 진실을 안다는게 전파 되어야함
• = 같은 그룹으로 만든다
  = 순서보다 같은 그룹에 속하는지...

2. Parent 리스트 생성 + 초기전파

 known_num, known_p = known_p[0], known_p[1:]
    for p in known_p:
        parent[p] = known_p[0]

입력받은 값 중에 제일 작은값으로 초기전파 시킴

3. 파티 입력 받을 때마다 Union(전파)

parties=[]
    for i in range(m):
        party = list(map(int, input().split()))
        party_num, party = party[0], party[1:]
        for i in range(party_num-1):
            union(party[i], party[i+1])
        parties.append(party)

예를 들어 4 1 2 5 6 입력했다면
union(4, 1)
union(1, 2)
union(2, 5)
union(5, 6) 이렇게 한다.

4. 이제 union시킨 parent를 가지고 허풍 떨지 말지 결정

1) 최적화 전

answer=0
    for p in parties:
        count=0
        for person in p:
            if find(person)==find(known_p[0]):
                break
            else:
                count+=1
        if count==len(p):         
            answer+=1
    print(answer)      

• 양쪽에 find를 씌우는 이유는 나중에 union 할때 초기값보다 더 작은 집합과 union 되면 그 값이 되기 때문.. 따라서 find 씌워주어야 한다.
  예를 들어 초기값이 3인덱스의 3하나인데 나중에 3과 2가 union이 될 수 있기 떄문임
  -> 결국 부모를 찾아나간다.
• 마지막 확인때 find는 거의 국룰...

2) 최적화 후

answer=0
    for p in parties:
        if find(p[0])==find(known_p[0]):
            continue    
        answer+=1
    print(answer) 

사실 생각해보면 이미 같은 집합끼리는 union 시켰기 때문에 첫번째 값만 확인하면 됨