2JINISHAPPY 2JINISHAPPY

이전에 Biconnected Component와 Cut Vertex에 대해 포스팅한 적이 있다 https://2jinishappy.tistory.com/169?category=903864 무방향그래프에서의 Cut Vertex와 Biconnected Components 우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포.. 2jinishappy.tistory.com 간단히 요약하자면 Cut Vertex: Connected Undirected Graph에서 특정 정점을 제거했을 때 2개 이상의 Conn..

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net SCC의 기본 문제이다 SCC(Strongly Connected Component)란 그래프 내의 특별한 Connected Component로, 해당 컴포넌트 안의 어떠한 노드 u와 v에 대해 반드시 path가 존재함을 말한다 따라서 directed graph 내에서만 존재할 수 있으며, 해당 SCC를 하나의 큰 노드로 가정..