SCC5 강한 연결 요소(SCC) 그래프에셔 u->v와 v->u 경로(간선아님)가 모두 있으면 같은 SCC에 속한다고 한다. dfs하면서 stack을 이용해서 분리해 낸다. 선형시간 O(n) 필요한 것: int id = 0, dfsn[MAX]={0}; //방문하는 정점마다 고유번호를 저장하기 위함. dfsn은 visit의 역할도 수행한다. bool finished[MAX] = {false}; //scc추출이 완료된 정점인지 vector adj[MAX] stack s 선택1) vector SCC; 선택2) int SN=0, sn[MAX]; //해당 정점이 포함된 scc번호를 저장함 int id, dfsn[MAX]; bool finished[MAX]; vector adj[MAX]; vector SCC; stack s; int makeSCC(.. 2019. 8. 19. 이전 1 2 다음