Is Graph Bipartite

Q: Is Graph Bipartite의 시간 복잡도는 얼마인가요?

너비 우선 또는 깊이 우선 색칠은 m 개의 간선에 대해 O(n + m) 시간에 실행됩니다. 모든 노드는 한 번씩 색칠되고, 모든 간선은 양쪽 끝에서 각각 한 번씩 비교됩니다. 인접 리스트와 색상은 O(n + m) 공간을 사용합니다. 유니온-파인드는 O(n + m α(n)) 시간에 같은 답을 구합니다.

보통그래프 큐

+10

그래프에는 0부터 n-1까지 레이블이 지정된 n개의 노드가 있습니다. edges의 각 [a, b] 쌍은 노드 a와 노드 b 사이의 무방향 간선입니다. 그래프는 여러 개의 분리된 부분으로 나뉠 수 있으며, 간선이 전혀 없는 노드가 있을 수도 있습니다.

모든 간선이 한 그룹의 노드와 다른 그룹의 노드를 연결하도록 노드를 두 그룹으로 나눌 수 있으면 그래프는 이분 그래프입니다. 그래프가 이분 그래프이면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

함수

isBipartite(n: integer, edges: integer-2d-array) → boolean

ninteger: 노드의 개수(0부터 n-1까지 번호가 매겨짐)
edgesinteger-2d-array: 무방향 간선들로, 각 간선은 [a, b] 쌍입니다
반환값boolean: 노드들을 두 그룹으로 나눌 수 있고 모든 간선이 두 그룹 사이에 있으면 true, 그렇지 않으면 false

제약 조건

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b]이며 0 ≤ a, b ≤ n-1이고 a ≠ b
어느 방향에서든 동일한 간선이 두 번 나타나지 않습니다.

예제

입력: n = 4edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
출력: true
설명: 노드 0과 2를 한 그룹에 넣고 노드 1과 3을 다른 그룹에 넣으세요. 네 개의 간선은 각각 두 그룹을 연결합니다.

입력: n = 6edges = [[0, 1], [2, 3], [3, 4], [4, 2]]
출력: false
설명: 간선 [0, 1]은 잘 분할되고 노드 5에는 간선이 없지만, 노드 2, 3, 4는 삼각형을 이룹니다. 한 부분이라도 조건을 만족하지 않으면 답은 false입니다.

후속 질문

그래프가 이분 그래프가 아닐 때, 증명으로 홀수 길이의 사이클 하나를 그 노드들을 순서대로 나열해 반환할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

한 노드의 그룹을 선택하면 연결된 부분의 나머지 노드도 결정됩니다. 이웃 노드는 다른 그룹에 속하게 됩니다. 너비 우선 탐색으로 각 부분을 두 색으로 번갈아 칠합니다. 양 끝 노드가 같은 색을 갖는 간선이 하나도 없을 때에만 그래프는 이분 그래프입니다. 그래프는 비연결 그래프일 수 있으므로, 색칠되지 않은 각 노드에서 새로운 탐색을 시작합니다.

모든 분할을 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

모든 분할을 시도하세요. 각 노드의 그룹을 하나의 비트로 취급하면 n개의 비트가 이진수를 이루고, 0부터 2^n-1까지 세면 모든 분할을 한 번씩 확인할 수 있습니다. 각 분할에 대해 모든 간선을 확인하고, 모든 간선이 분할을 가로지르게 하는 분할이 있으면 true를 반환하세요. 노드가 하나 늘어날 때마다 분할 수는 두 배가 됩니다. 노드가 20개라면 약 백만 개입니다.

알고리즘

0부터 2^n-1까지의 각 숫자에 대해, 비트 i가 나타내는 그룹에 노드 i를 넣습니다.
모든 간선이 두 그룹을 연결하면 true를 반환합니다.
가능한 분할이 없으면 false를 반환합니다.

def isBipartite(n, edges):
    side = [0] * n  # side[x] is 0 or 1: the group of node x in the current split
    while True:
        # Does every edge cross between the two groups?
        if all(side[u] != side[v] for u, v in edges):
            return True
        # Move to the next split, counting in binary over side.
        i = 0
        while i < n and side[i] == 1:
            side[i] = 0
            i += 1
        if i == n:
            return False  # all 2^n splits have been tried
        side[i] = 1

각 노드의 이웃에서의 유니온-파인드

핵심 아이디어

노드가 어느 그룹에 속하든 모든 이웃은 다른 그룹에 속하므로, 서로 같은 그룹을 공유합니다. 각 노드에 대해 모든 이웃을 하나의 유니온-파인드 집합으로 합칩니다. 그러면 한 집합에는 같은 쪽에 놓일 수밖에 없는 노드들이 담깁니다. 양 끝점이 모두 하나의 집합에 속한 간선은 그룹 내부에 머물 수밖에 없으므로, 그래프는 이분 그래프가 아닙니다.

이 검사는 모든 실패를 포착합니다. 홀수 사이클에서는 한 번에 두 간선씩 합치면 첫 번째 노드와 마지막 노드가 연결되고, 사이클을 닫는 간선이 그 둘을 합칩니다. 홀수 사이클이 없다면 모든 합치기는 짝수 거리만큼 떨어진 두 노드를 합치므로, 두 노드는 같은 쪽에 놓입니다. 노드의 첫 번째 이웃인 기준 노드는 그 노드의 이웃들이 속한 집합을 가리킵니다. 따라서 인접 리스트 없이 간선이 들어오는 대로 합치면 됩니다. 크기 기준 유니온과 경로 절반 줄이기를 사용하면 2m번의 합치기와 m번의 검사는 O(m α(n))의 비용이 듭니다.

알고리즘

모든 노드에 대해 parent[x] = x 및 anchor[x] = -1로 설정합니다.
각 간선 [u, v]에 대해, 아직 앵커가 없는 각 끝점에 반대쪽 끝점을 앵커로 지정합니다.
v를 anchor[u]의 집합에 병합하고, u를 anchor[v]의 집합에 병합합니다.
어떤 간선의 양 끝점이 하나의 집합에 있으면 false를 반환하고, 그렇지 않으면 true를 반환합니다.

def isBipartite(n, edges):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n
    anchor = [-1] * n  # the first neighbour seen for each node

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    # All neighbours of a node must sit on one side: the side opposite the node.
    for u, v in edges:
        if anchor[u] == -1:
            anchor[u] = v
        if anchor[v] == -1:
            anchor[v] = u
        union(anchor[u], v)  # v joins the other neighbours of u
        union(anchor[v], u)  # u joins the other neighbours of v
    # An edge whose two ends were forced onto one side cannot cross.
    for u, v in edges:
        if find(u) == find(v):
            return False
    return True

모든 부분의 너비 우선 2색 칠하기

핵심 아이디어

충돌은 결정적입니다. 한 부분의 첫 번째 색은 자유롭게 선택할 수 있고, 그 색을 뒤집으면 부분 전체의 색이 뒤집힙니다. 나머지 모든 색은 간선에 의해 정해집니다. 탐색은 시작점으로부터의 거리가 짝수인지 홀수인지에 따라 노드에 색을 칠하므로, 두 이웃이 같은 색을 갖는 경우는 해당 부분에 홀수 길이의 사이클이 있을 때뿐이며, 이 경우에는 분할이 존재하지 않습니다.

탐색은 자신이 속한 부분만 확인하므로, 모든 노드를 살펴보고 아직 색칠되지 않은 각 노드에서 새로운 탐색을 시작하세요. 세 번째 예제에서 노드 0에서 시작한 탐색은 노드 0과 1에 색을 칠합니다. 노드 2에서 시작한 탐색은 노드 2에 색 0을, 노드 3과 4에 색 1을 칠한 다음, 양 끝이 모두 색 1인 [3, 4]를 찾아 false를 반환합니다. 각 노드는 한 번씩 색칠되고 큐에 추가되며, 목록의 2m개 항목은 각각 한 번씩 비교됩니다. 시간과 공간 복잡도는 O(n + m)입니다.

알고리즘

각 간선을 양쪽 끝점 모두의 인접 리스트에 추가하고, 모든 색을 -1로 설정합니다.
순서대로 색이 지정되지 않은 각 노드에 색 0을 지정하고 큐에 넣습니다.
노드를 꺼냅니다. 색이 지정되지 않은 각 이웃에는 반대 색을 지정하고 큐에 넣습니다. 이웃의 색이 같으면 false를 반환합니다.
모든 부분에 색이 지정되면 true를 반환합니다.

from collections import deque


def isBipartite(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    color = [-1] * n  # -1: not colored yet, otherwise 0 or 1
    for start in range(n):
        if color[start] != -1:
            continue
        # A new component: its first node can take either color.
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in graph[node]:
                if color[nxt] == -1:
                    # A neighbour must take the other color.
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # this edge stays inside one group
    return True

함정과 경계 사례

노드 0에서만 탐색하기. 세 번째 예시는 노드 0 주변에서는 올바르게 작동하지만 노드 2, 3, 4 사이에서는 실패합니다.
각 간선을 하나의 목록에만 추가하기. 간선 [1, 0]과 [2, 0]이 있을 때 노드 0은 색상 0을 받고 이웃을 보지 못합니다. 그런 다음 노드 1도 색상 0을 받고, 노드 0으로 이어지는 간선이 충돌처럼 보이지만 경로는 문제없이 두 그룹으로 나뉩니다.
노드를 꺼낼 때 색칠하기. 그러면 노드가 큐에 두 번 들어갈 수 있고, 두 번째 방문이 첫 번째 색상을 덮어씁니다. 노드를 큐에 넣을 때 색칠하세요.
이분 그래프와 비순환 그래프를 혼동하기. 정사각형에는 사이클이 있지만 이분 그래프입니다. 홀수 사이클만 두 그룹으로 나누는 것을 방해합니다.

자주 묻는 질문3

Is Graph Bipartite의 시간 복잡도는 얼마인가요?

너비 우선 또는 깊이 우선 색칠은 m개의 간선에 대해 O(n + m) 시간에 실행됩니다. 모든 노드는 한 번씩 색칠되고, 모든 간선은 양쪽 끝에서 각각 한 번씩 비교됩니다. 인접 리스트와 색상은 O(n + m) 공간을 사용합니다. 유니온-파인드는 O(n + m α(n)) 시간에 같은 답을 구합니다.

홀수 사이클이 그래프를 이분 그래프가 아니게 만드는 이유는 무엇인가요?

사이클을 따라 이동하면 그룹이 번갈아 나타나야 합니다. 첫 번째, 두 번째, 첫 번째, 두 번째와 같이 말입니다. 간선 수가 홀수인 사이클에서는 홀수 번 그룹을 바꾼 뒤 시작점으로 돌아오므로, 시작점은 두 그룹 모두에 속해야 합니다. 그래프는 홀수 길이의 사이클이 없을 때, 그리고 그럴 때에만 이분 그래프입니다.

그래프가 이분 그래프인지 확인할 때 BFS를 사용해야 할까요, 아니면 DFS를 사용해야 할까요?

둘 다 작동합니다. 색칠 규칙은 같고 방문 순서만 달라집니다. 큰 그래프에서는 재귀 버전이 노드마다 호출 깊이가 하나씩 증가할 수 있으므로 명시적인 스택을 사용해 DFS를 작성하세요.

def isBipartite(n, edges):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

n = 4
edges = [[0, 1], [1, 2], [2, 3], [3, 0]]

예상 출력

true

Is Graph Bipartite

함수

제약 조건

예제

힌트

풀이

모든 분할을 시도해 보세요

각 노드의 이웃에서의 유니온-파인드

모든 부분의 너비 우선 2색 칠하기

함정과 경계 사례

자주 묻는 질문3

비슷한 문제