Chương trình C++ tìm số điểm chia (Articulation Points) trong đồ thị

Điểm chia (Articulation Points hay Cut Vertices) trong đồ thị là đỉnh mà nếu xóa nó (và các cạnh qua nó) sẽ làm đồ thị không liên thông. Đối với đồ thị vô hướng không liên thông, điểm chia là đỉnh mà khi xóa làm tăng số thành phần liên thông.

Thuật toán

Bắt đầu
  Dùng DFS tìm điểm chia:
  Trong DFS, đỉnh w là điểm chia nếu thỏa một trong hai điều kiện:
    1) w là gốc của cây DFS và có ít nhất hai con.
    2) w không phải gốc và có con x sao cho không đỉnh nào trong cây con gốc x
       có cạnh ngược (back edge) đến tổ tiên của w trong cây.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
#include <list>
#define N -1
using namespace std;

class G {
    int n;
    list<int> *adj;
    void APT(int v, bool visited[], int dis[], int low[], int par[], bool ap[]);
public:
    G(int n);
    void addEd(int w, int x);
    void AP();
};

G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int w, int x) {
    adj[x].push_back(w);
    adj[w].push_back(x);
}

void G::APT(int w, bool visited[], int dis[], int low[], int par[], bool ap[]) {
    static int t = 0;
    int child = 0;
    visited[w] = true;
    dis[w] = low[w] = ++t;
    list<int>::iterator i;
    for (i = adj[w].begin(); i != adj[w].end(); ++i) {
        int x = *i;
        if (!visited[x]) {
            child++;
            par[x] = w;
            APT(x, visited, dis, low, par, ap);
            low[w] = min(low[w], low[x]);
            // w là điểm chia trong các trường hợp sau:
            // w là gốc DFS và có >= 2 con
            if (par[w] == N && child > 1)
                ap[w] = true;
            // w không phải gốc và low[x] >= dis[w]
            if (par[w] != N && low[x] >= dis[w])
                ap[w] = true;
        } else if (x != par[w])
            low[w] = min(low[w], dis[x]);
    }
}

void G::AP() {
    bool *visited = new bool[n];
    int *dis = new int[n];
    int *low = new int[n];
    int *par = new int[n];
    bool *ap = new bool[n];
    for (int i = 0; i < n; i++) {
        par[i] = N;
        visited[i] = false;
        ap[i] = false;
    }
    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            APT(i, visited, dis, low, par, ap);
    for (int i = 0; i < n; i++)
        if (ap[i] == true)
            cout << i << " ";
}

int main() {
    cout << "\nĐiểm chia (Articulation points) trong đồ thị đầu tiên \n";
    G g1(5);
    g1.addEd(1, 2);
    g1.addEd(3, 1);
    g1.addEd(0, 2);
    g1.addEd(2, 3);
    g1.addEd(0, 4);
    g1.AP();
    return 0;
}

Kết quả

Điểm chia (Articulation points) trong đồ thị đầu tiên
0 2