Graph - Cycle 여부 확인하기

Graph 기타 알고리즘
graph - 서로소 집합 확인하기 -> 재귀함수를 이용해서 루트 노드 확인하기
이를 활용하여 Cycle 유무를 확인할 수 있다.

💻 코드

import java.util.*;

public class relatively_prime
{
    public static int v, e;
    public static int[] parent = new int[100001]; // 부모 테이블 초기화

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x)
    {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;

        // 경로 압축
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b)
    {
        a = findParent(a);
        b = findParent(b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 부모 테이블에서, 부모를 자기 자신으로 초기화
        for(int i = 1; i <= v; i++)
        {
            parent[i] = i;
        }

        // Union 연산을 각각 수행
        for (int i = 0; i < e; i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            unionParent(a, b);
        }

        System.out.println("각 원소가 속한 집합 : ");
        for(int i = 1; i <= v; i++)
        {
            System.out.print(findParent(i) + " ");
        }
        System.out.println();

        // 부모 테이블 내용 출력하기
        System.out.println("부모 테이블 : ");
        for (int i = 1; i <= v; i++)
        {
            System.out.println(parent[i] + " ");
        }
        System.out.println();

        boolean cycle = false; // 사이클 발생 여부

        for (int i = 0; i < e; i++)
        {
            int a = sc.nextInt();
            int b = sc.nextInt();

            // 사이클이 발생하는 경우 종료
            if (findParent(a) == findParent(b)) {
                cycle = true;
                break;
            }

            else
                unionParent(a, b);
        }

        if(cycle) System.out.println("사이클 발생");
        else System.out.println("사이클 비발생");

    }

}

📝 정리

서로소 집합은 무방향 그래프 내에서의 사이클 유무를 판별하는데 사용 가능

• 1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인
     1) 루트 노드가 다르다면 두 노드에 대해 Union 연산 실행
     2) 루트 노드가 같다면 사이클로 판별
• 2. 그래프에 포함한 모든 노드에 대해 위 과정 반복