단절점1 이중 연결 요소(BCC), 단절점, 단절선 SCC와 다르게 무향그래프에서 사용되는 개념 ㅁ BCC 어떤 BCC안에 속한 정점 하나와 그 정점에 인접한 간선들을 지웠을 때, 그 BCC 내에 남은 정점들은 모두 연결됨. (SCC와 유사, 하지만 간선끼리 묶어서 분류) 한번의 dfs로 BCC를 분류할 수 있다. int n, m, vst[MAX], counter; vector g[MAX]; vector bcc; //P는 간선 표현 stack s; int makeBCC(int u, int p) { int ret = vst[u] = counter++; for (int v : g[u]) if (v != p) { //아직 방문하지 않은 간선인 경우 스택에 u-v간선 넣음 if (vst[u] > vst[v]) s.push({ u,v }); //트리간선 if (v.. 2020. 2. 13. 이전 1 다음
