Tổng quan thuật toán Tarjan

Thành phần liên thông mạnh

Mở code

#include <bits/stdc++.h>

using namespace std;

int soDinh, soCanh;
vector<int> dsKe[10005];

int dfn[10005], low[10005], boDemThoiGian;
int nganXep[10005], dinhNganXep;
bool dangTrongXep[10005];
int soThanhPhan, thuocThanhPhan[10005];
vector<int> thanhPhan[10005];
bool daXuat[10005];

void tarjan(int dinh) {
    dfn[dinh] = low[dinh] = ++boDemThoiGian;
    nganXep[++dinhNganXep] = dinh;
    dangTrongXep[dinh] = true;
    
    for (auto ke : dsKe[dinh]) {
        if (!dfn[ke]) {
            tarjan(ke);
            low[dinh] = min(low[dinh], low[ke]);
        } else if (dangTrongXep[ke]) {
            low[dinh] = min(low[dinh], dfn[ke]);
        }
    }

    if (low[dinh] == dfn[dinh]) {
        soThanhPhan++;
        int temp;
        do {
            temp = nganXep[dinhNganXep--];
            dangTrongXep[temp] = false;
            thuocThanhPhan[temp] = soThanhPhan;
            thanhPhan[soThanhPhan].push_back(temp);
        } while (temp != dinh);
    }
}

int main() {
    cin >> soDinh >> soCanh;
    for (int i = 0; i < soCanh; i++) {
        int u, v;
        cin >> u >> v;
        dsKe[u].push_back(v);
    }

    for (int i = 1; i <= soDinh; i++)
        if (!dfn[i]) tarjan(i);

    cout << soThanhPhan << endl;
    for (int i = 1; i <= soDinh; i++) {
        if (daXuat[thuocThanhPhan[i]]) continue;
        daXuat[thuocThanhPhan[i]] = true;
        sort(thanhPhan[thuocThanhPhan[i]].begin(), thanhPhan[thuocThanhPhan[i]].end());
        for (auto x : thanhPhan[thuocThanhPhan[i]])
            cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

Rút gọn đồ thị

Mở code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int soDinh, soCanh;
ll trongSo[10005];
struct Canh {
    int u, v;
} dsCanh[100005];
vector<int> dsKe[10005];
vector<int> dsRutGon[10005];
ll trongSoRutGon[10005];

int dfn[10005], low[10005], boDemThoiGian;
int nganXep[10005], dinhNganXep;
bool dangTrongXep[10005];
int thuocThanhPhan[10005];
int soThanhPhan;
ll tongTrongSo[10005];

void dfs(int dinh) {
    dfn[dinh] = low[dinh] = ++boDemThoiGian;
    nganXep[++dinhNganXep] = dinh;
    dangTrongXep[dinh] = true;
    
    for (auto ke : dsKe[dinh]) {
        if (!dfn[ke]) {
            dfs(ke);
            low[dinh] = min(low[dinh], low[ke]);
        } else if (dangTrongXep[ke]) {
            low[dinh] = min(low[dinh], dfn[ke]);
        }
    }

    if (low[dinh] == dfn[dinh]) {
        soThanhPhan++;
        int temp;
        do {
            temp = nganXep[dinhNganXep--];
            dangTrongXep[temp] = false;
            tongTrongSo[soThanhPhan] += trongSo[temp];
            thuocThanhPhan[temp] = soThanhPhan;
        } while (temp != dinh);
    }
}

int bacVao[10005];
ll ketQua[10005];

int main() {
    cin >> soDinh >> soCanh;
    for (int i = 1; i <= soDinh; i++)
        cin >> trongSo[i];
    for (int i = 0; i < soCanh; i++) {
        int u, v;
        cin >> u >> v;
        dsCanh[i] = {u, v};
        dsKe[u].push_back(v);
    }

    for (int i = 1; i <= soDinh; i++)
        if (!dfn[i]) dfs(i);

    for (int i = 0; i < soCanh; i++) {
        if (thuocThanhPhan[dsCanh[i].u] != thuocThanhPhan[dsCanh[i].v]) {
            int u = thuocThanhPhan[dsCanh[i].u];
            int v = thuocThanhPhan[dsCanh[i].v];
            dsRutGon[u].push_back(v);
            bacVao[v]++;
        }
    }

    for (int i = 1; i <= soThanhPhan; i++)
        trongSoRutGon[i] = tongTrongSo[i];

    queue<int> hangDoi;
    for (int i = 1; i <= soThanhPhan; i++)
        if (bacVao[i] == 0) {
            ketQua[i] = trongSoRutGon[i];
            hangDoi.push(i);
        }

    while (!hangDoi.empty()) {
        int u = hangDoi.front(); hangDoi.pop();
        for (auto v : dsRutGon[u]) {
            ketQua[v] = max(ketQua[v], ketQua[u] + trongSoRutGon[v]);
            bacVao[v]--;
            if (bacVao[v] == 0) hangDoi.push(v);
        }
    }

    ll maxKetQua = 0;
    for (int i = 1; i <= soThanhPhan; i++)
        maxKetQua = max(maxKetQua, ketQua[i]);
    cout << maxKetQua;
    
    return 0;
}

Điểm khớp

Mở code

#include <bits/stdc++.h>

using namespace std;

int soDinh, soCanh;
vector<int> dsKe[20005];

int dfn[20005], low[20005], boDemThoiGian;
int soDiemKhop, laDiemKhop[20005];

void tarjan(int dinh, int goc) {
    dfn[dinh] = low[dinh] = ++boDemThoiGian;
    
    int conTre = 0;
    for (auto ke : dsKe[dinh]) {
        if (!dfn[ke]) {
            conTre++;
            tarjan(ke, goc);
            low[dinh] = min(low[dinh], low[ke]);
            if (low[ke] >= dfn[dinh] && dinh != goc)
                if (!laDiemKhop[dinh]) {
                    soDiemKhop++;
                    laDiemKhop[dinh] = 1;
                }
        } else {
            low[dinh] = min(low[dinh], dfn[ke]);
        }
    }

    if (dinh == goc && conTre >= 2)
        if (!laDiemKhop[dinh]) {
            soDiemKhop++;
            laDiemKhop[dinh] = 1;
        }
}

int main() {
    cin >> soDinh >> soCanh;
    for (int i = 0; i < soCanh; i++) {
        int u, v;
        cin >> u >> v;
        dsKe[u].push_back(v);
        dsKe[v].push_back(u);
    }

    for (int i = 1; i <= soDinh; i++)
        if (!dfn[i]) tarjan(i, i);

    cout << soDiemKhop << endl;
    for (int i = 1; i <= soDinh; i++)
        if (laDiemKhop[i]) cout << i << " ";
    
    return 0;
}

Thành phần liên thông chập (đỉnh)

Mở code

#include <bits/stdc++.h>

using namespace std;

int soDinh, soCanh;
vector<int> dsKe[500005];

int dfn[500005], low[500005], boDemThoiGian;
int nganXep[500005], dinhNganXep;
int soThanhPhan;
vector<int> thanhPhan[500005];

void tarjan(int dinh, int goc) {
    dfn[dinh] = low[dinh] = ++boDemThoiGian;
    nganXep[++dinhNganXep] = dinh;
    
    int conTre = 0;
    for (auto ke : dsKe[dinh]) {
        if (!dfn[ke]) {
            conTre++;
            tarjan(ke, goc);
            low[dinh] = min(low[dinh], low[ke]);
            
            if (low[ke] >= dfn[dinh]) {
                soThanhPhan++;
                int temp;
                do {
                    temp = nganXep[dinhNganXep--];
                    thanhPhan[soThanhPhan].push_back(temp);
                } while (temp != ke);
                thanhPhan[soThanhPhan].push_back(dinh);
            }
        } else {
            low[dinh] = min(low[dinh], dfn[ke]);
        }
    }

    if (dinh == goc && conTre == 0)
        thanhPhan[++soThanhPhan].push_back(dinh);
}

int main() {
    cin >> soDinh >> soCanh;
    for (int i = 0; i < soCanh; i++) {
        int u, v;
        cin >> u >> v;
        dsKe[u].push_back(v);
        dsKe[v].push_back(u);
    }

    for (int i = 1; i <= soDinh; i++)
        if (!dfn[i]) {
            dinhNganXep = 0;
            tarjan(i, i);
        }

    cout << soThanhPhan << endl;
    for (int i = 1; i <= soThanhPhan; i++) {
        cout << thanhPhan[i].size() << " ";
        for (auto x : thanhPhan[i]) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

Thành phần liên thông chập (cạnh)

Mở code

#include <bits/stdc++.h>

using namespace std;

int soDinh, soCanh, soCanhHuong;
vector<pair<int, int>> dsKe[500005];

int dfn[500005], low[500005], boDemThoiGian;
int soThanhPhan;
vector<int> thanhPhan[500005];
int nganXep[500005], dinhNganXep;

void tarjan(int dinh, int canh) {
    dfn[dinh] = low[dinh] = ++boDemThoiGian;
    nganXep[++dinhNganXep] = dinh;
    
    for (auto ke : dsKe[dinh]) {
        if (!dfn[ke.first]) {
            tarjan(ke.first, ke.second);
            low[dinh] = min(low[dinh], low[ke.first]);
        } else if (ke.second != (canh ^ 1)) {
            low[dinh] = min(low[dinh], dfn[ke.first]);
        }
    }

    if (low[dinh] == dfn[dinh]) {
        soThanhPhan++;
        int temp;
        do {
            temp = nganXep[dinhNganXep--];
            thanhPhan[soThanhPhan].push_back(temp);
        } while (temp != dinh);
    }
}

int main() {
    cin >> soDinh >> soCanh;
    for (int i = 0; i < soCanh; i++) {
        int u, v;
        cin >> u >> v;
        dsKe[u].push_back({v, soCanhHuong++});
        dsKe[v].push_back({u, soCanhHuong++});
    }

    for (int i = 1; i <= soDinh; i++)
        if (!dfn[i]) {
            dinhNganXep = 0;
            tarjan(i, -1);
        }

    cout << soThanhPhan << endl;
    for (int i = 1; i <= soThanhPhan; i++) {
        cout << thanhPhan[i].size() << " ";
        for (auto x : thanhPhan[i]) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

Không sử dụng ngăn xếp cho: điểm khớp, thành phần liên thông chập (đỉnh)

Thẻ: thuat-toan-tarjan do-thi-lien-thong thanh-phan-lien-thong-manh diem-khop canh-cau

Đăng vào ngày 29 tháng 6 lúc 05:36

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn