← 22주차 · 유니온 파인드와 MST
보통유니온 파인드그래프

그래프 사이클 판정

정점 개수 n과 무방향 간선 목록 edges가 주어져요. 정점은 0번부터 n-1번까지 있어요. 이 그래프에 사이클이 있으면 true, 없으면 false를 반환해요.

간선을 하나씩 보면서, 두 끝점이 이미 같은 무리에 속해 있다면 그 간선이 무리를 한 바퀴 잇는 셈이라 사이클이 생겨요. 아직 다른 무리면 둘을 합쳐요.

자기 자신을 잇는 간선(self-loop)도 사이클로 봐요.

예시

예시 1
입력
n = 3, edges = [[0, 1], [1, 2], [2, 0]]
출력
true
설명
0-1-2-0으로 한 바퀴 도는 사이클이 있어요.
예시 2
입력
n = 4, edges = [[0, 1], [1, 2], [2, 3]]
출력
false
설명
한 줄로 이어져 있어 사이클이 없어요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 200,000
  • 0 ≤ a, b < n
parent를 자기 자신으로 시작해요. 각 간선의 두 끝점 대표를 찾아 같으면 사이클이니 바로 true를 반환하고, 다르면 두 무리를 합쳐요. 모든 간선을 봐도 걸리지 않으면 false예요.
javascript
function graphCycle(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  for (const [a, b] of edges) {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return true;
    parent[ra] = rb;
  }
  return false;
}
이전 문제유니온 파인드 구현
다음 문제크루스칼 MST
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.