[BOJ 7987/10542] Spies/MAFIJA

문제: https://www.acmicpc.net/problem/7987 / https://www.acmicpc.net/problem/10542

 

풀이 (7987):

indegree가 0인 정점 $d$와 $d$가 가리키는 $a_d$가 모두 선택되지 않은 답이 있으면, $a_{a_d}$를 선택하지 않고 $a_d$를 선택하는 것으로 답을 옮길 수 있습니다. 이후에 $d$와 $a_d$는 그래프의 다른 성분에 영향을 미치지 않으므로 제거해도 됩니다. 즉, $d$와 $a_d$를 찾아서 아무거나 제거하는 것을 반복하면 스파이를 최적의 방법으로 배치할 수 있습니다.

 

이제 indegree가 0인 정점이 없는 사이클인 경우만 남고, 각 사이클의 길이를 $C$라고 하면 $\left\lfloor C/2 \right\rfloor$의 합을 구하면 됩니다.

풀이 (10542):

7987과 비슷한 아이디어를 사용합니다. indegree가 0인 정점 $d$가 선택되지 않으면, $a_d$를 선택하지 않고 $d$를 선택하는 것으로 답을 옮길 수 있습니다. 여기서는 $a_d$를 선택하지 못한다고 체크 해 주고, 계속 로직을 반복해주면 됩니다. 만약 $a_d$가 indegree가 0이면 그 때 삭제해주면 됩니다.

코드 (7987): https://www.acmicpc.net/source/share/cd96ea36b23a47d5b0ddc2e201d257cc

코드 (10542): https://www.acmicpc.net/source/share/40666c2a19e649d4baaf5d60878704fa