절단점, 절단선, 이중 결합 요소

절단점과 절단선

• 무향 그래프에서 한 정점, 그리고 그 정점과 인접한 간선들을 제거했을 때 그래프가 둘 이상으로 나뉘는 정점을 의미한다.
• 비슷하게, 간선이 없어지면 그래프가 둘 이상으로 나뉘는 간선을 절단선이라고 한다.

절단점 찾기

vi adj[MAX];
bool iscut[MAX];
int dist[MAX], cnt=0; // dist -> -1로 초기화

int dfsCut(int here, bool isRoot) {
    int ret = dist[here] = cnt++;

    // 루트인경우, 자식이 2개 이상이면 절단점이다.
    int child = 0;
    for (int go : adj[here]) {

        if (dist[go] == -1) {
            child++;
            int highest = dfsCut(go, false);
            if (!isRoot && dist[here] <= highest)
                iscut[here] = true;
            ret = min(ret, highest);
        }
        else
            ret = min(ret, dist[go]);
    }

    if (isRoot) iscut[here] = child >= 2;
    return ret;
}

• 관련문제
  BOJ 11266

절단선 찾기

vi adj[MAX];
int dist[MAX], cnt=0; // dist -> -1로 초기화
vector<pii> ans;

int dfsCut2(int here, int parent) {
    int ret = dist[here] = cnt++;

    for (int go : adj[here]) {

        if (dist[go] == -1) {
            int highest = dfsCut(go, here);
            if (dist[here] < highest) {
                int a = here, b = go;
                if (a > b) swap(a, b);
                ans.emplace_back(a, b);
            }
                
            ret = min(ret, highest);
        }
        else if (go!=parent)
            ret = min(ret, dist[go]);
    }

    return ret;
}

• 관련문제
  BOJ 11400

이중 결합 요소 (BCC)

• BCC내 한 정점과 그 정점에 인접한 간선을 제거해도 서로 연결되있는 그룹을 BCC라고 한다. 이중, 즉 서로 연결돼있는 경로가 두개 이상이라는 뜻이다. 그리고 그래프 내 BCC는 절단점에 의해서 구분된다. 절단점은 제거하게 되면 그래프가 단절된다는 뜻이므로 절단점이 두 그룹을 연결하는 유일한 경로라는 뜻이다. 경로가 두가지 이상이 아니므로 절단점을 기준으로 BCC가 구분되는 것을 쉽게 이해할 수 있다. 절단점같은 경우 여러 BCC에 동시에 포함되므로 bcc를 저장할 때 정점대신 간선들의 집합을 저장한다.

• 사이클과 관계가 깊다. 두개 이상의 간선을 포함하는 bcc는 bcc의 모든 정점을 연결하는 사이클이 존재한다.

간단하게 증명해보자. 우선 간선이 하나인 경우는 절단선이고 양 끝의 정점은 절단점이니 넘어가자. 간선이 두개 이상이면 반드시 3개 이상의 정점이 bcc에 포함된다.

3개 이상의 정점을 포함하는 bcc에서 임의의 두 정점 u, v가 있다. u, v를 연결하는 경로는 bcc의 정의에 의해서 2개 이상이다. 그럼 u에서 첫번째 경로를 따라 v로, v에서 다시 두번째 경로를따라 u로 돌아오는 사이클이 반드시 존재한다. 즉, bcc내부의 모든 두 정점은 임의의 사이클에 속한다.

그럼, bcc의 점들을 v1, v2.. vn이라고 할 때, v1->v2..->vn->v1인 경로가 반드시 존재한다. 즉 모든 정점을 포함하는 사이클 역시 존재한다.

그 사이클이 단순사이클일까? 어떻게 판단할 수 있을까? bcc에 속하는 간선의 개수와 정점의 개수를 비교하면 알 수 있지 않을까..?

BCC 구하기

typedef pair<int,int> pii;
vi adj[MAX]; 
vector<vector<pii>> bcc; //bcc의 간선들이 담겨있다.
int dist[MAX], cnt = 0;
stack<pii> s;

int dfsBcc(int here, int parent) {
    int ret = dist[here] = cnt++;

    for (int go : adj[here]) {
        if (go == parent) continue;
        // 트리간선, 역방향 간선만 스택에 넣음
        // 나중에 돌아와서 이미 넣은 역방향 간선을 위에서 순방향 간선으로 다시 넣지않도록
        if (dist[here] > dist[go]) s.emplace(here, go);

        if (dist[go] == -1) {
            int highest = dfsBcc(go, here);
            ret = min(ret, highest);

            if (dist[here] <= highest) {
                bcc.push_back(vector<pii>());
                vector<pii>& cur = bcc.back();
                // (here -> go)까지만 넣는다
                while (!s.empty() && s.top() != pii(here, go)) {
                    cur.push_back(s.top()); s.pop();
                }
                cur.push_back(s.top()); s.pop();
            }
        }
        else
            ret = min(ret, dist[go]);
    }

    return ret;
}

• 관련문제
  BOJ 10891

정점이 속해있는 BCC의 개수 구하기

vi adj[MAX]; //init
int dist[MAX], bcc[MAX]; // init
int cnt=0;

int dfsCut(int here, bool isRoot) {
    int ret = dist[here] = cnt++;

    // 루트의경우 부모가 없으므로 0에서 시작
    int cnt = (isRoot) ? 0 : 1;
    for (int go : adj[here]) {

        if (dist[go] == -1) {
            int highest = dfsCut(go, false);
            if (!isRoot && dist[here] <= highest)
                cnt++;
            ret = min(ret, highest);
        }
        else
            ret = min(ret, dist[go]);
    }
    // here에 속해있는 bcc의 개수 
	bcc[here] = cnt;
    return ret;
}

각 정점이 몇개의 bcc에 속하는지 구하는 알고리즘. 2개 이상의 bcc에 속하면 절단점이다.

• 관련문제
  BOJ 6672