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

Đề bàihttp://vn.spoj.com/problems/GRAPH_/

Code C++ (Nộp với C++14 – gcc 6.4):
(Tham khảo từ Competitive Programming 3 và blog kc97ble)
Độ phức tạp O(M + N)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n, m;
vector<int> a[10005];
int cnt = 0, low[10005], num[10005], isPoint[10005];
int points = 0, bridges = 0;

void dfs(int u, int p) {
    int children = 0;
    num[u] = low[u] = cnt++;
    for(int v : a[u]) {
        if (num[v] == -1) {
            children++;
            dfs(v, u);

            // u "may" be articulation point
            if (low[v] >= num[u])
                isPoint[u] = (u == p) ? (children > 1) : 1;

            // u-v is bridges
            if (low[v] > num[u]) bridges++;

            low[u] = min(low[u], low[v]);
        } else if (v != p)
            low[u] = min(low[u], num[v]);
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {         
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    memset(num, -1, sizeof num);
    memset(low, 0, sizeof low);
    memset(isPoint, 0, sizeof isPoint);
    for(int u = 1; u <= n; u++)
        if (num[u] == -1) dfs(u, u);
    for(int u = 1; u <= n; u++) points += isPoint[u];

    cout << points << ' ' << bridges;

    return 0;
}

Ghi chú:
– num[u]: là thứ tự duyệt dfs đến đỉnh u
– low[u]: là num nhỏ nhất trong tập những đỉnh mà u có thể đi đến.
Khởi tạo thì low[u] = num[u], low[u] sẽ thay đổi khi có một cạnh tạo nên chu trình trong đồ thị.

– Như vậy, xét một cạnh u-v:
+ Nếu low[v] >= num[u] thì u là khớp
+ Nếu low[v] > num[u] thì u-v là cầu

– Corner case:
Đỉnh u được chọn để duyệt dfs đầu tiên, thì với mọi v kề u, ta đều có low[v] >= num[u], trong khi nó chưa chắc đã là khớp.
Trong trường hợp này, u sẽ là khớp nếu(số_con_của_cây_DFS(u) > 1).

Happy coding

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s