코사라주 알고리즘 썸네일형 리스트형 SCC(Strongly Connected Component) 방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에.. 더보기 BOJ)2150 Strongly Connected Component 문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo.. 더보기 이전 1 다음
