연결 요소, 사이클, 위상성 검사

그래프 검증 문제는 결국 세 가지 질문으로 모입니다. 몇 개로 나뉘는가(연결 요소), 순환이 있는가(사이클), 순서를 만들 수 있는가(위상성)입니다. 겉으로는 다른 문제처럼 보이지만 공통 기반은 방문 상태 정의입니다.

이 검사를 따로 구현하면 조건을 섞어 쓰는 실수가 자주 발생합니다. 아래에서는 세 검사를 한 흐름으로 묶어 같은 상태 규칙을 재사용하도록 구성했습니다. 상태만 정확히 잡으면 코드가 길어도 논리를 안정적으로 유지할 수 있습니다.

핵심 패턴 프레임

검증 문제는 알고리즘 이름보다 상태 배열을 어떻게 잡는지가 더 중요합니다. 지금 문제에서 필요한 상태 배열(visited, state, indegree 등)을 우선 써 놓고 읽어 보세요.

연결 요소는 서로 도달 가능한 정점들의 묶음입니다. 무방향 그래프에서 경로로 연결된 정점의 최대 부분집합을 하나의 컴포넌트로 봅니다. 1-2-3과 4-5가 분리되어 있다면 연결 요소 수는 2개입니다.

사이클 상태(DFS color/state)는 정점 진행 상태를 미방문/방문중/완료로 구분하는 규칙입니다. 방향 그래프 DFS에서 방문중 정점을 다시 만나는 back-edge를 사이클 신호로 사용할 수 있습니다. 탐색 중 state=1 정점에 재진입하면 사이클이 있다고 판정합니다.

위상성 검사는 정점을 선행 관계대로 줄 세울 수 있는지 확인하는 절차입니다. Kahn 알고리즘에서 진입 차수 0 정점을 계속 제거해 처리 수가 V와 같으면 DAG입니다. 처리한 정점 수가 전체보다 작으면 사이클 때문에 유효한 위상 순서를 만들 수 없습니다.

연결요소/사이클 실전 장애와 연결하기

의존성 그래프, 배포 순서, 작업 스케줄링에서 이 검사는 필수입니다.
연결 요소를 잘못 계산하면 분리 배포 단위를 잘못 잡을 수 있고, 사이클을 놓치면 배포가 멈출 수 있습니다.

따라서 성능보다 정확한 상태 규칙이 우선입니다.

그래프 상태 테스트로 빠르게 검증하기

학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.

작은 그래프에서 검증 항목 3가지를 순서대로 확인합니다.

무방향 그래프: 연결 요소 개수 확인
방향 그래프: DFS 상태(미방문/방문중/완료)로 사이클 검사
DAG 후보: Kahn 처리 정점 수가 전체 정점 수와 같은지 확인

연결 요소 수가 기대값과 다르면 모델링 오류 가능성이 큽니다.
DFS 중 방문중 정점 재진입은 사이클 신호입니다.
Kahn에서 처리 정점이 모자라면 사이클이 존재합니다.

그래프 판정: 연결 요소 개수

문제 의도: 무방향 그래프를 컴포넌트 단위로 분리해 개수를 계산합니다.
입력 예시: n=5, edges=[(1,2),(2,3),(4,5)]
출력 예시: 2

main.cpp

#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

int countComponents(int n, const vector<pair<int, int>>& edges) {
    unordered_map<int, vector<int>> graph;
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    unordered_set<int> visited;
    int comp = 0;
    for (int node = 1; node <= n; ++node) {
        if (visited.count(node)) continue;
        comp++;
        queue<int> q;
        q.push(node);
        visited.insert(node);
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (int nxt : graph[cur]) {
                if (visited.count(nxt)) continue;
                visited.insert(nxt);
                q.push(nxt);
            }
        }
    }
    return comp;
}

int main() {
    cout << countComponents(5, {{1, 2}, {2, 3}, {4, 5}}) << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static int countComponents(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }

        Set<Integer> visited = new HashSet<>();
        int comp = 0;
        for (int node = 1; node <= n; node++) {
            if (visited.contains(node)) continue;
            comp++;
            Queue<Integer> q = new ArrayDeque<>();
            q.offer(node);
            visited.add(node);
            while (!q.isEmpty()) {
                int cur = q.poll();
                for (int nxt : graph.getOrDefault(cur, List.of())) {
                    if (visited.contains(nxt)) continue;
                    visited.add(nxt);
                    q.offer(nxt);
                }
            }
        }
        return comp;
    }

    public static void main(String[] args) {
        System.out.println(countComponents(5, new int[][]{{1,2},{2,3},{4,5}}));
    }
}

main.py

from collections import defaultdict, deque

def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    comp = 0

    for node in range(1, n + 1):
        if node in visited:
            continue

        comp += 1
        q = deque([node])
        visited.add(node)

        while q:
            cur = q.popleft()
            for nxt in graph[cur]:
                if nxt in visited:
                    continue
                visited.add(nxt)
                q.append(nxt)

    return comp

print(count_components(5, [(1,2), (2,3), (4,5)]))  # 2

main.rs

use std::collections::{HashMap, HashSet, VecDeque};

fn count_components(n: i32, edges: &[(i32, i32)]) -> i32 {
    let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
    for &(u, v) in edges {
        graph.entry(u).or_default().push(v);
        graph.entry(v).or_default().push(u);
    }

    let mut visited = HashSet::new();
    let mut comp = 0;
    for node in 1..=n {
        if visited.contains(&node) {
            continue;
        }
        comp += 1;
        let mut q = VecDeque::new();
        q.push_back(node);
        visited.insert(node);
        while let Some(cur) = q.pop_front() {
            for &nxt in graph.get(&cur).unwrap_or(&Vec::new()) {
                if visited.contains(&nxt) {
                    continue;
                }
                visited.insert(nxt);
                q.push_back(nxt);
            }
        }
    }
    comp
}

fn main() {
    println!("{}", count_components(5, &[(1, 2), (2, 3), (4, 5)]));
}

연결/사이클/위상 결과 그래프 모델 조건 검토

탐색 시작 횟수가 곧 연결 요소 수입니다.
이미 방문한 정점은 건너뛰므로 중복 계산이 없습니다.
고립 노드도 하나의 연결 요소로 포함해야 정확합니다.

평균 시간복잡도: O(V + E)
최악 시간복잡도: O(V + E)
공간복잡도: O(V)

그래프 판정: 방향 그래프 사이클 검사(DFS 상태)

문제 의도: DFS 3상태(미방문/방문중/완료)로 방향 그래프 사이클을 감지합니다.
입력 예시: 1->2->3->1 포함 그래프
출력 예시: true(사이클 있음)

main.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

bool dfs(int node, const unordered_map<int, vector<int>>& graph, unordered_map<int, int>& state) {
    state[node] = 1;
    auto it = graph.find(node);
    if (it != graph.end()) {
        for (int nxt : it->second) {
            int s = state.count(nxt) ? state[nxt] : 0;
            if (s == 1) return true;
            if (s == 0 && dfs(nxt, graph, state)) return true;
        }
    }
    state[node] = 2;
    return false;
}

bool hasCycleDirected(const unordered_map<int, vector<int>>& graph) {
    unordered_map<int, int> state;
    for (auto& [node, _] : graph) {
        if (!state.count(node) && dfs(node, graph, state)) return true;
    }
    return false;
}

int main() {
    unordered_map<int, vector<int>> g1 = {{1, {2}}, {2, {3}}, {3, {1}}, {4, {5}}};
    cout << hasCycleDirected(g1) << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static boolean dfs(int node, Map<Integer, List<Integer>> graph, Map<Integer, Integer> state) {
        state.put(node, 1);
        for (int nxt : graph.getOrDefault(node, List.of())) {
            int s = state.getOrDefault(nxt, 0);
            if (s == 1) return true;
            if (s == 0 && dfs(nxt, graph, state)) return true;
        }
        state.put(node, 2);
        return false;
    }

    static boolean hasCycleDirected(Map<Integer, List<Integer>> graph) {
        Map<Integer, Integer> state = new HashMap<>();
        for (int node : graph.keySet()) {
            if (state.getOrDefault(node, 0) == 0 && dfs(node, graph, state)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g1 = Map.of(
            1, List.of(2),
            2, List.of(3),
            3, List.of(1),
            4, List.of(5)
        );
        System.out.println(hasCycleDirected(g1));
    }
}

main.py

def has_cycle_directed(graph):
    state = {}  # 0: 미방문, 1: 방문중, 2: 완료

    def dfs(node):
        state[node] = 1
        for nxt in graph.get(node, []):
            s = state.get(nxt, 0)
            if s == 1:
                return True
            if s == 0 and dfs(nxt):
                return True
        state[node] = 2
        return False

    for node in graph:
        if state.get(node, 0) == 0 and dfs(node):
            return True
    return False

g1 = {1:[2], 2:[3], 3:[1], 4:[5]}
print(has_cycle_directed(g1))  # True

main.rs

use std::collections::HashMap;

fn dfs(node: i32, graph: &HashMap<i32, Vec<i32>>, state: &mut HashMap<i32, i32>) -> bool {
    state.insert(node, 1);
    if let Some(nxts) = graph.get(&node) {
        for &nxt in nxts {
            let s = *state.get(&nxt).unwrap_or(&0);
            if s == 1 {
                return true;
            }
            if s == 0 && dfs(nxt, graph, state) {
                return true;
            }
        }
    }
    state.insert(node, 2);
    false
}

fn has_cycle_directed(graph: &HashMap<i32, Vec<i32>>) -> bool {
    let mut state = HashMap::new();
    for &node in graph.keys() {
        if *state.get(&node).unwrap_or(&0) == 0 && dfs(node, graph, &mut state) {
            return true;
        }
    }
    false
}

fn main() {
    let mut g1 = HashMap::new();
    g1.insert(1, vec![2]);
    g1.insert(2, vec![3]);
    g1.insert(3, vec![1]);
    g1.insert(4, vec![5]);
    println!("{}", has_cycle_directed(&g1));
}

연결/사이클/위상 결과 방문 순서 추적

방문중 상태를 다시 만나는 순간 백엣지가 발견되고, 이는 사이클을 의미합니다.
방문완료(2) 상태는 다시 탐색할 필요가 없습니다.
이 3상태 모델을 정확히 지키면 방향 그래프 사이클 검사가 안정적으로 동작합니다.

평균 시간복잡도: O(V + E)
공간복잡도: O(V)

그래프 판정: 위상성 검사(Kahn)

문제 의도: 진입 차수 기반 Kahn 알고리즘으로 DAG 여부를 판정합니다.
입력 예시: DAG 간선 집합, 사이클 그래프 간선 집합
출력 예시: DAG는 true, 사이클 그래프는 false

main.cpp

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

bool isDag(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> graph(n + 1);
    vector<int> indeg(n + 1, 0);
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (indeg[i] == 0) q.push(i);
    }

    int seen = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        seen++;
        for (int nxt : graph[cur]) {
            indeg[nxt]--;
            if (indeg[nxt] == 0) q.push(nxt);
        }
    }
    return seen == n;
}

int main() {
    cout << isDag(4, {{1, 2}, {2, 3}, {1, 3}, {3, 4}}) << "\n";
    cout << isDag(3, {{1, 2}, {2, 3}, {3, 1}}) << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static boolean isDag(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[n + 1];

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph.get(u).add(v);
            indeg[v]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);

        int seen = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            seen++;
            for (int nxt : graph.get(cur)) {
                indeg[nxt]--;
                if (indeg[nxt] == 0) q.offer(nxt);
            }
        }
        return seen == n;
    }

    public static void main(String[] args) {
        System.out.println(isDag(4, new int[][]{{1,2},{2,3},{1,3},{3,4}}));
        System.out.println(isDag(3, new int[][]{{1,2},{2,3},{3,1}}));
    }
}

main.py

from collections import defaultdict, deque

def is_dag(n, edges):
    graph = defaultdict(list)
    indeg = [0] * (n + 1)

    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1

    q = deque([i for i in range(1, n + 1) if indeg[i] == 0])
    seen = 0

    while q:
        cur = q.popleft()
        seen += 1
        for nxt in graph[cur]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

    return seen == n

print(is_dag(4, [(1,2), (2,3), (1,3), (3,4)]))  # True
print(is_dag(3, [(1,2), (2,3), (3,1)]))         # False

main.rs

use std::collections::VecDeque;

fn is_dag(n: usize, edges: &[(usize, usize)]) -> bool {
    let mut graph = vec![Vec::new(); n + 1];
    let mut indeg = vec![0usize; n + 1];
    for &(u, v) in edges {
        graph[u].push(v);
        indeg[v] += 1;
    }

    let mut q = VecDeque::new();
    for i in 1..=n {
        if indeg[i] == 0 {
            q.push_back(i);
        }
    }

    let mut seen = 0usize;
    while let Some(cur) = q.pop_front() {
        seen += 1;
        for &nxt in &graph[cur] {
            indeg[nxt] -= 1;
            if indeg[nxt] == 0 {
                q.push_back(nxt);
            }
        }
    }
    seen == n
}

fn main() {
    println!("{}", is_dag(4, &[(1, 2), (2, 3), (1, 3), (3, 4)]));
    println!("{}", is_dag(3, &[(1, 2), (2, 3), (3, 1)]));
}

연결/사이클/위상 결과 경로/사이클 재확인

진입 차수 0 노드를 계속 제거했을 때 모든 노드를 방문하면 DAG입니다.
일부 노드가 남으면 순환이 존재해 위상 순서를 만들 수 없습니다.
배포 순서 검증과 작업 의존성 검사에서 매우 실용적인 방법입니다.

평균 시간복잡도: O(V + E)
공간복잡도: O(V + E)

연결/위상 판정 구조 운용 관점

검사 목적에 따라 접근을 나눕니다.

그래프가 몇 덩어리인지: 연결 요소
순환 존재 여부: DFS 상태 or Kahn
실제 순서 생성 가능 여부: 위상 정렬 기반 검사

목적을 우선 고정하면 불필요한 계산을 줄일 수 있습니다.

사이클 검사와 위상 검사 구현 복잡도 상충

검사 방식 간 균형점입니다.

DFS 상태 검사: 구현 간결, 재귀 깊이 주의
Kahn 방식: 순서 생성과 검사 동시 가능, 진입 차수 배열 필요
BFS/DFS 연결 요소: 둘 다 가능, 팀 익숙한 방식 선택

같은 정답이라도 운영 환경 제약(스택 한계, 메모리)으로 선택이 달라질 수 있습니다.

방문 상태 오답 패턴과 교정 방법

그래프 검증에서 자주 틀리는 지점입니다.

방향/무방향 혼동
정점 집합 누락(키에 없는 노드)
indegree 초기화 오류
사이클 없는 그래프를 순환으로 오탐(상태 갱신 누락)

반례는 고립 노드, 단일 사이클, 다중 컴포넌트를 모두 포함해야 합니다.

간선 밀도와 입력 분포 판단

같은 정답이라도 입력 분포에 따라 병목 지점이 달라지므로, 선택 관점을 시간복잡도 표 하나로 끝내지 말고 분포 가정까지 명시해야 합니다.

작업	평균 시간	최악 시간	공간
연결 요소 계산	`O(V+E)`	`O(V+E)`	`O(V)`
DFS 사이클 검사	`O(V+E)`	`O(V+E)`	`O(V)`
Kahn 위상성 검사	`O(V+E)`	`O(V+E)`	`O(V)`

세 검사는 상한이 비슷하므로 정확한 상태 설계가 더 중요합니다.

제출 직전 방향성/사이클 체크

큰 그래프에서 재귀 DFS는 반복 구현으로 바꾸는 것이 안전합니다.
인덱스 시작(0-based/1-based)을 통일하지 않으면 결과가 왜곡됩니다.
검증 함수는 입력 불변성을 유지하도록 내부 복사 정책을 명확히 해야 합니다.
운영 로그에는 실패한 정점/간선 정보를 함께 기록해야 원인 분석이 쉽습니다.

실무 적용 요약

연결 요소, 사이클, 위상성 검사는 배포 파이프라인 검증의 기본 세트로 사용할 수 있습니다.
세 검사를 같은 입력 모델 위에서 실행하면 장애 원인을 단계별로 빠르게 좁힐 수 있습니다.
특히 위상성 실패 시 관련 간선을 함께 출력하면 운영 대응 속도가 크게 올라갑니다. 이 일관된 검증 루틴은 대규모 시스템에서 회귀 오류를 줄이는 데 큰 효과가 있습니다.

제출 전 그래프 검증 체크리스트

무방향/방향 그래프 처리 규칙을 혼동 없이 분리했는가
DFS 상태값 갱신 순서를 정확히 지켰는가
Kahn 처리 정점 수와 전체 정점 수를 비교했는가
고립 노드/단일 사이클/다중 컴포넌트 반례를 검증했는가

그래프 구조 판정 정리

연결성, 순환성, 위상성 검사는 같은 상태 관리 문제의 다른 얼굴입니다.
상태 규칙을 정확히 정의하면, 그래프 검증 문제를 일관된 틀로 안정적으로 해결할 수 있습니다.

연결 요소, 사이클, 위상성 검사

목차