전체 글 썸네일형 리스트형 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.. 더보기 BOJ)3176 도로 네트워크 문제: icpc.me/3176 N개의 도시와 그 도시를 연결하는 N-1개의 도로 네트워크가 있을 때 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하는 문제이다. 우리는 모든 도시 쌍에는 그 도시를 연결하는 유일한 경로가 있다는데에서 주어진 그래프가 트리임을 유추할 수 있다. 우리는 문제를 해결하기 위하여 LCA를 이용할 것이다. 우리는 LCA를 구할 때 두 도시의 2^i번째 부모를 저장한다. 이 때 우리는 2^i번째 부모를 저장할 뿐만 아니라 x번째 정점 기준으로 2^i번째 부모까지의 모든 간선중에 최솟값과 최댓값을 같이 저장할 수 있다. 이를 이용하여 쿼리를 처리하면 문제를 해결할 수 있다. 1234567891011121314151617181920212223242.. 더보기 이전 1 ··· 89 90 91 92 93 94 95 ··· 118 다음
