2JINISHAPPY 2JINISHAPPY

우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포함해야하며, 하나라도 더 추가한 순간 disconnected해야한다)를 의미한다. 여기에서 사이클에 대한 조건을 추가한 개념이 Biconnected Component(BCC)라고 할 수 있다. 위의 그림과 같은 무방향 간선 (연결) 그래프가 있다고 가정하자. 이 상태에서 vertex A 및 A와 연결된 모든 edge를 삭제하면 그래프는 (D,G,H)와 (B,C,E,F,I,J)로 분리된 disconnected graph가 된다. 이렇게 해당 그래프에서..