SCC

강한 연결 요소 (Strongly Connected Component, SCC)강한 연결 요소(SCC)란 방향 그래프에서 어떤 두 점 u와 v가 있을 때 u -> v와 v -> u 두 방향으로 모두 경로가 존재하는 정점들의 최대 집합을 의미한다.특징SCC는 방향 그래프의 구성 요소무방향 그래프에서의 연결 요소와 비슷하지만, 방향성이 존재하는 그래프에서 정의된다.SCC 내의 모든 정점은 서로 도달 가능해야 한다.DAG로 변환 가능모든 SCC를 하나의 정점으로 압축하면 방향성이 없는 비순환 그래프 (DAG, Directed Acyclic Graph)가 만들어진다.이 DAG는 SCC의 상호 연결 관계를 보여준다.응용SCC는 그래프 분석, 순환 검출, 도미노 문제, 인터넷 네트워크 분석, 강한 결합성을 가진 시..

코드 (코사라주 알고리즘)#include #include #include #include #include #include #include #include #include using namespace std;const int MAX_N = 10003;int v, e, a, b, cnt = 1, visited[MAX_N];bool finished[MAX_N];vector adj[MAX_N], radj[MAX_N];vector> res;stack stk;void dfs(int x) { visited[x] = 1; for(int i : adj[x]) { if(!visited[i]) { dfs(i); } } stk.push(x);}void dfs2..