[BOJ] 15511번: League of Overwatch at Moloco

https://www.acmicpc.net/problem/15511


주어진 그래프를 이분그래프로 분할할 수 있는지를 묻고 있습니다. 그룹을 A, B라고 할 때 아직 그룹에 편입시키지 못한 임의의 노드에 대해 아래와 같은 작업을 반복합니다.


1) 택한 노드를 A에 편입

2) 그 노드로부터 BFS(혹은 DFS)를 돌면서 노드를 택함

3-1) 택한 노드가 이미 그룹에 편입되어있고, 부모 노드와 같은 그룹에 편입된 경우 불가능

3-2) 택한 노드가 이미 그룹에 편입되어있고, 부모 노드와 다른 그룹에 편입된 경우 일단 계속 진행

3-3) 택한 노드가 그룹에 편입되어있지 않을 경우 부모 노드와 다른 그룹에 편입시킴


이것을 그룹에 편입시키지 못한 노드가 없을 때 까지 반복합니다. 정상적으로 종료될 경우 주어진 그래프는 이분그래프로 분할 가능합니다.


https://github.com/blisstoner/BOJ/blob/master/15511.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1033번: 칵테일  (0) 2018.03.11
[BOJ] 6236번: 용돈 관리  (0) 2018.03.07
[BOJ] 15515번: Tap Titanz at Moloco  (0) 2018.03.05
[BOJ] 15509번: Xayahh-Rakann at Moloco  (0) 2018.03.05
[BOJ] 15549, 15550번 (if, if 2)  (0) 2018.03.05
[BOJ] 1030번: 프렉탈 평면  (0) 2018.02.20
  Comments