BCC 정점 기준으로

간선 기준으로 BCC 를 나누는 것은 구글에 치면 있기에 정점 기준 BCC 를 쓸려고 합니다.

나중에 까먹지 않을라고 쓰는 것이 큽니다.

 

알고리즘은 간단합니다.

 

dfs를 돌면서 어떤 정점에서 역방향 간선이 있으면 그곳은 사이클이 있기 마련입니다.

그랬을 때 역방향 간선이 가르키는 정점의 부모 정점 이하의 지나왔던 정점은 사이클일 것입니다.

그리고 그 역방향 간선이 가르키는 정점과 부모 정점 끼리 또 사이클을 만들면 그 전 사이클에다 추가해야 될 것입니다.

이 것이 알고리즘의 끝입니다.

코딩이 중요한데 stack으로 관리합니다.

stack 두개로 관리하면서 한 개는 지나온 정점 두 번째는 지나온 정점이긴 하지만 사이클이 없는 제일 마지막 정점(?) 이라 생각하면 되겠습니다.

그럼 스택 두 번째에서 사이클이 없는 제일 마지막 정점에서 역방향 간선이 없다면 제일 마지막 정점 ~ 첫 번째에서 마지막 정점은 사이클일 것 이고 하나의 BCC 를 이룰 것입니다.

이런 식으로 구현 해주면 되겠습니다.

 

코드입니다.

void dfs(int cur, int prev, int &k) {  
        order[cur] = ++k;  
        S.push(cur); inS[cur] = true;  
        roots.push(cur);  
  
        for(auto to: g[cur]) {  
            if(order[to]==0) dfs(to, cur, k);  
            else if(to != prev && inS[to]) {  
                while(order[roots.top()] > order[to]) roots.pop();  
            }  
        }  
  
        if(cur == roots.top()) {  
            if(prev!=-1) bridge.push_back({prev, cur});  
            vector<int> bcc;  
            while(1) {  
                int node = S.top(); S.pop(); inS[node] = false;  
                bcc.push_back(node);  
                if(node == cur) break;  
            }  
            each_bcc.push_back(bcc);  
            roots.pop();  
        }  
    }  

제가 짠 코드는 아닙니다. 참고한 코드입니다.

 

 while(order[roots.top()] > order[to]) roots.pop();

이 부분에서 curr이 아닌 to 기준으로 잡는 이유는

어떤 정점에서 사이클을 가르키면서 사이클을 만드는 경우는 존재하지 않기 때문입니다.

왜냐하면 양방향 간선이기 때문에 어떤 정점에서 사이클을 가르킨 다는 것은

사이클이 만들어지고 나서 그 정점으로 갔다는 것이고

애초에 사이클에서 먼저 그 정점으로 방문을 했기 때문입니다.

즉 그 정점이랑 사이클이랑 합쳐져서 더 큰 사이클을 만들었다고 가정했을 때엔

그 정점에서 사이클을 가르키는 경우는 애초에 같은 사이클이기 때문에 상관안써도되는 경우입니다.