白駿1707|二分図(DFS&BFS)

問題のソース:https://www.acmicpc.net/problem/1707

質問する

グラフィック頂点のセットを2つに分けると、隣接するすべてのノード間のセットの異なるグラフィックを2つのグラフと呼びます.
グラフィック頂点の個数と幹線情報が与えられると
このグラフはこちらのグラフですか.そうですか.出力の問題.

入力

k:テストケース数(1<=k<=5)
v:頂点数(1<=v<=2000)
e:幹線数(2つの頂点の番号、1<=e<=20000)

問題の処理方法

最初は質問で説明されているこのグラフが何なのか分からなかったので、ウィキペディアを参照.
上の図に示すように、集合情報を色で表現すると分かりやすいようです.

BFSを用いた実施手順

宣言格納集合情報(コードでステータスstatusとして表される)のリスト
(0:まだグループ化されていません.1:青、2:赤)

開始ノードからBFSを迂回して親ノードと子ノードのstatusを決定する.
1)子ノードの状態がない場合、親ノードの状態とは逆になります.status[child] = -status[parent]2)子ノードの状態が親ノードの状態と同じである場合、二分図ではないため、Falseが返される.

すべてのノードが接続されていない可能性があるので、すべてのノードがまだステータスstatusを持っていない場合、そのノードを先頭ノードとしてBFSが行われる.

せきぶん

コレクション情報statusを表示するには、
他のDFS&BFSの問題とは異なり、アクセスされたノードについても、集合情報statusを表示する必要がある.
(アレイへのアクセスは不要)

すべてのノードが接続されていない可能性があります.
各ノードについて、ステータスstatusが0の場合、BFSを実行してノードをグループ化する必要がある.

BFSコード

import sys
from collections import deque

def bfs(x):

    # 탐색 시작 노드를 큐에 넣고 초기 상태를 1로 설정한다.
    queue = deque()
    queue.append(x)

    status[x] = 1

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            # 아직 상태가 없을 경우 부모 노드와 반대로 설정한다.
            if status[i] == 0:
                status[i] = -status[v]
                queue.append(i)
            else:
                # 이전에 상태를 이미 지정해줬는데 
                # 부모노드와 자식노드의 상태가 같다면 
                # 이분 그래프가 아니므로 False를 반환한다.
                if status[i] == status[v]:
                    return False

    return True
            

k = int(sys.stdin.readline())

for _ in range(k):
    # v : 정점의 개수, e : 간선의 개수
    v, e = map(int, sys.stdin.readline().split())
    
    # graph : 인접 노드 정보, visited : 방문 정보, status : 집합 정보 
    graph = [[] for _ in range(v + 1)]
    status = [0] * (v + 1)

    # 간선의 정보 입력 받음
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    """
    (주의) 모든 노드가 연결되어 있지 않고 떨어져 있을 때를 생각해야한다.
    (입력 예시) 
        1 (테스트 케이스 개수)
        2 (간선 개수)
        1 3 (긴선 정보, 1과 3이 연결되어 있다)
        4 5 (긴선 정보, 4와 5가 연결되어 있다)
    이렇게 떨어져 있는 그래프 일 수 있으므로 각 노드 별로 
    인접 노드중에 같은 집합이 있는지를 bfs를 통해 확인한다.
    """
    flag = True
    
    for i in range(1, v + 1):
        if status[i] == 0:
            if not bfs(i):
                flag = False
    
    if flag:
        print('YES')
    else:
        print('NO')

いっそ落ちたグラフとは思えない.もっと問題をやりましょう.