알고리즘

[C++] 코사라주( Kosaraju ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )

코사라주( Kosaraju ) 알고리즘코사라주 알고리즘은 방향 그래프에서 강한 연결 요소( SCC )를 구하는 알고리즘입니다.여기서, 강한 연결 요소는 주어진 방향 그래프에서 임의의 두 정점을 선택했을 때, 그 두 정점 간에 경로가 존재하는 최대 부분 집합입니다. 이와 같은 알고리즘으로는 타잔( Tarjan ) 알고리즘이 있습니다.강한 연결 요소와 타잔 알고리즘은 자세한 내용은 여기에서 볼 수 있습니다. [C++] 타잔( Tarjan ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )강한 연결 요소( Strongly Connected Component, SCC )강한 연결 요소는 방향 그래프에서 모든 정점에 도달하는 경로가 존재하는 최대 부분 집합을 말합니다.다른 말로..

2024. 7. 14.

문제 풀이/백준 (BOJ)

[백준/BOJ] 2150번: Strongly Connected Component ( SCC 타잔 알고리즘 ) - C++ 문제 풀이

문제 설명 문제 링크: https://www.acmicpc.net/problem/2150 풀이이 문제는 방향 그래프가 주어졌을 때, 그 안에 존재하는 강한 연결 요소( Strongly Connected Component, SCC )를 구해 출력하는 문제입니다. 강한 연결 요소는 방향 그래프에서 임의의 두 정점을 선택하더라도, 두 정점 간에 경로가 존재하는 최대 부분 집합을 말합니다. 이러한 강한 연결 요소를 구하는 알고리즘이 두 가지 있는데,하나는 코사라주( Kosaraju ) 알고리즘이고, 다른 하나는 타잔( Tarjan ) 알고리즘입니다. 이 문제에서는 타잔 알고리즘을 사용해서 문제를 풀었습니다.강한 연결 요소와 타잔 알고리즘에 관한 내용은 여기에 정리해 두었습니다. [C++] 타잔( Tarjan )..

2024. 7. 14.

알고리즘

[C++] 타잔( Tarjan ) 알고리즘 ( Strongly Connected Component, SCC 구하기 )

강한 연결 요소( Strongly Connected Component, SCC )강한 연결 요소는 방향 그래프에서 모든 정점에 도달하는 경로가 존재하는 최대 부분 집합을 말합니다.다른 말로 하면, 강한 연결 요소는 순환 경로가 있는 부분 집합을 뜻합니다. 아래의 이미지를 보면  1과, 2번, 3번 정점 중, 어떤 두 정점을 선택해도, 한 정점에서 다른 정점으로 도달할 수 있는 경로가 존재합니다.반면, 3번에서 출발하여 4번 정점엔 도달할 수 있지만, 4번 정점에서 3번 정점으로는 이동할 수 없습니다.따라서, { 1, 2, 3 } 집합이 가장 크면서 서로 경로가 존재하는 부분 집합입니다.이 부분 집합을 강한 연결 요소( strongly connected component )라고 합니다.이 그래프에서는 강한..

2024. 7. 9.