let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

ADS - Quảng cáo

solution.md

Bài này ta cần đếm số chu trình cơ bản của đồ thị đã cho. Công thức là M-N+1 cho mỗi thành phần liên thông. Ngoài ra ta có thể DFS để đếm số cạnh nối ngược lên trên trong quá trình DFS.

Code dsu.cpp sử dụng disjoin set để kết hợp việc tìm các TPLT với đếm số cạnh và đỉnh trong TPLT. Rồi dùng công thức M-N+1 để tính kết quả.

Code dfs.cpp dùng DFS như đã nói ở trên.

dsu.cpp
Open in Github • Download 
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;

struct dsu {
    vector<int> cha, rank, n, m;
    dsu(int N): cha(N+1), n(N+1), m(N+1) {
        for (int i=1; i<=N; i++) {
            cha[i] = i;
            m[i] = 0;
            n[i] = 1;
        }
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    void join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) {
            m[u]++;
            return;
        }
        if (rand()&1) swap(u, v);
        cha[v] = u;
        n[u] += n[v];
        m[u] += m[v] + 1;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m; 
    dsu d(n);
    while (m--) {
        int u, v; cin >> u >> v;
        d.join(u, v);
    }
    int res = 0;
    for (int i=1; i<=n; i++) if (d.cha[i] == i) res += d.m[i] - d.n[i] + 1;
    cout << res;
    return 0;
}
dfs.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int>> dsk;
bool visited[2001], instack[2001];
int dfs(int u, int cha, dsk &ke) {
    visited[u] = true;
    instack[u] = true;
    int res = 0;
    for (int v: ke[u]) if (v != cha) {
        if (instack[v]) res++;
        if (!visited[v]) res += dfs(v, u, ke);
    }
    instack[u] = false;
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    dsk ke(n+1);
    while (m--) {
        int u, v; cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    int res = 0;
    for (int u=1; u<=n; u++) if (!visited[u]) res += dfs(u, 0, ke);
    cout << res;
    return 0;
}
Comments