bridge.cpp (deprecated)

Bài viết này cũ, hãy đọc bài viết mới hơn

https://sites.google.com/site/kc97ble/algorithm-graph/tim-khop-va-cau

Tìm khớp và cầu trong đồ thị vô hướng

Mục đích : Tìm các cạnh hoặc các đỉnh mà khi loại bỏ chúng, đồ thị sẽ bị chia làm nhiều đồ thị con hơn (chính xác là nhiều thành phần liên thông hơn).

Độ phức tạp : O(n) hay O(|V|+|E|) (số cạnh cộng số đỉnh)

bridge.cpp

#include <stdio.h>

#include <vector>

using namespace std;

const int oo = 1000111000;

vector<int> a[2309];

int n, m;

int num[2309];

int low[2309];

int parent[2309];

int numChild[2309];

int cnt;

void minimize(int &a, int b) {

    if (a > b) a = b;

}

void visit(int u) {

    num[u] = ++cnt;

    low[u] = oo;

    for (int v : a[u])

        if (v == parent[u])

            continue;  // keep direction

        else if (num[v] > 0)

            minimize(low[u], num[v]);

        else {

            parent[v] = u;

            visit(v);

            minimize(low[u], low[v]);

        }

}

void visit() {

    for (int i = 1; i <= n; i++)

        if (num[i] == 0) {

            parent[i] = -1;

            visit(i);

        }

}

void show() {

    printf("node   : ");

    for (int i = 1; i <= n; i++) printf("%3d,", i);

    printf("\n");

    printf("num    : ");

    for (int i = 1; i <= n; i++) printf("%3d,", num[i]);

    printf("\n");

    printf("low    : ");

    for (int i = 1; i <= n; i++) printf("%3d,", low[i]);

    printf("\n");

    printf("parent : ");

    for (int i = 1; i <= n; i++) printf("%3d,", parent[i]);

    printf("\n");

    for (int v = 1; v <= n; v++)  // load all dfs edge

    {

        int u = parent[v];

        if (u == -1) continue;

        numChild[u]++;

        if (low[v] >= num[v]) printf("bridge (%d-%d)\n", u, v);

    }

    for (int v = 1; v <= n; v++) {

        int u = parent[v];

        if (u == -1) {  // if v is root

            if (numChild[v] >= 2) printf("cut node (%d)\n", v);

        } else if (low[v] >= num[u]) {

            if (parent[u] != -1)  // if u is not root

                printf("cut vertex (%d)\n", u);

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

    while (m--) {

        int p, q;

        scanf("%d%d", &p, &q);

        a[p].push_back(q);

        a[q].push_back(p);

    }

    visit();

    show();

}

Sample Input

4 4

1 2

2 3

3 4

4 2

Sample Output

node   :   1,  2,  3,  4,

num    :   1,  2,  3,  4,

low    :   2,  2,  2,  2,

parent :  -1,  1,  2,  3,

bridge (1-2)

cut vertex (2)

Thông tin khác

Ở bài viết này mình chỉ trình bày thuật toán tìm khớp và cầu ở đồ thị vô hướng, mong các bạn lưu ý.