Graph

• 인접 리스트 adj[]
• 방문 리스트 visit[]
• 편의
  • 부모 리스트 parent[]
  • 루트 리스트 root[] - union-find용
• 반전 그래프 (방향 그래프에서)
  • n번의 다익스트라를 2번으로 줄이는 기법
• 사이클
  • 사이클이 없는 것 → 트리
  • 사이클 판별법
    • 무향 그래프
      • union-find
        • 간선 추가시 이미 같은 그룹이라면 사이클

        •   bool unionSet(int a, int b) {
                int rootA = find(a);
                int rootB = find(b);
            
                if (rootA == rootB) return true; // ❌ 이미 같은 그룹이면 사이클 발생
            
                parent[rootB] = rootA; // 두 집합을 합침
                return false;
            }

      • dfs
        • 방문한 노드가 다시 나왔는데, 부모가 아니라면 사이클
    • 방향 그래프
      • 위상 정렬
        • 한 그룹이 안돌아지면
        • (진입 차수 - 1)
        • 진입 차수가 0인 노드를 큐에 넣고, 큐에서 노드를 하나씩 꺼내어 그 노드와 연결된 모든 노드의 진입 차수를 감소시킵니다.
        • 이 과정에서 진입 차수가 0인 노드가 더 이상 없다면 그래프에 사이클이 존재하는 것입니다.