Thuật toán Kruskal tìm cây khung nhỏ nhì

Code C++:
Độ phức tạp: O(VE)

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <set>
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int oo = 1e10;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ii> edge;

int n, m, lab[1005];
vector<edge> edges, mst_edges;

int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}

void merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}

ll scan_edges(int _u = 0, int _v = 0) {
    memset(lab, -1, sizeof lab);
    
    ll min_cost = 0;
    for(auto e : edges) {
        int u = e.se.fi;
        int v = e.se.se;
        ll w = e.fi;
        if (u == _u && v == _v) continue;
        if (root(u) != root(v)) {
            merge(u, v);
            min_cost += w;
            if (_u == _v) mst_edges.pb(e);
        }
    }
    
    set<int> roots;
    for(int u = 1; u <= n; u++) roots.insert(root(u));
    if (roots.size() != 1) return oo;
    return min_cost;
}

int main() {
    
    // reset
    edges.clear(); mst_edges.clear();
    memset(lab, -1, sizeof lab);
    
    // input
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        edges.pb(mp(w, mp(u, v)));
    }
    
    // modify Kruskal
    sort(edges.begin(), edges.end());
    
    cout << "MST: " << scan_edges() << '\n';
    ll mincost2 = oo;
    for(edge e : mst_edges)
        mincost2 = min(mincost2, scan_edges(e.se.fi, e.se.se));
    cout << "MST2: " << mincost2;
    
    return 0;
}

Input:

5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

Output:

MST: 110
MST2: 121

Happy coding,

Advertisements

Thuật toán Kruskal tìm cây khung nhỏ nhất (Minimum Spanning Tree)

Đề bài: http://vn.spoj.com/problems/QBMST/

Code C++:
Độ phức tạp: O(ElogV) = O(MlogN)

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long ll;

int n, m, lab[10005];
vector<pair<ll, pair<int, int> > > edges;
ll sum, mincost;

int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}

void merge(int u, int v) {
    u = root(u); v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}

int main() {
    
    // reset
    edges.clear();
    sum = 0; mincost = 0;
    memset(lab, -1, sizeof lab);
    
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        edges.pb(mp(w, mp(u, v)));
        sum += w;
    }
    
    sort(edges.begin(), edges.end());
    for(auto e : edges) {
        ll w = e.fi;
        int u = e.se.fi;
        int v = e.se.se;
        if (root(u) != root(v)) {
            merge(u, v);
            mincost += w;
        }
    }
    
    cout << mincost;
    
    return 0;
}

Happy coding

Union-Find Disjoint Sets (DSU)

Input:

4 2
1 2
2 3

Output:

1 2 3 4 
1 1 1 4

Code C++
Độ phức tạp:
Hàm root : O(logN)
Hàm merge : O(logN)

#include <iostream>
using namespace std;

int lab[1005];

int root(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = root(lab[u]);
}

void merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}

int main() {
    
    memset(lab, -1, sizeof lab);
    
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        merge(u, v);
    }
    
    for(int u = 1; u <= n; u++) cout << u << ' ';
    cout << '\n';
    for(int u = 1; u <= n; u++) cout << root(u) << ' ';
        
    return 0;
}

Ghi chú:
– Ý nghĩa mảng lab[], xét đỉnh u trong 1 thành phần liên thông:
+ Nếu u không phải là gốc (root) thì lab[u] = cha của u
+ Nếu u là gốc thì lab[u] < 0 và |lab[u]| = số lượng đỉnh của thành phần liên thông đó
Khởi tạo lab[u] = -1 với mọi u

– Tại mọi thời điểm, muốn truy vấn cha của u, phải dùng root(u) thay cho lab[u] (vì lab[u] lúc này có thể chưa được "nén")

– Khi merge thì ta sẽ nối thành phần liên thông có ít đỉnh hơn vào thành phần liên thông có nhiều đỉnh hơn, vì như vậy sẽ làm cho thuật toán nén đường ở hàm root tối ưu hơn.

Happy coding,

Thuật toán Tarjan tìm thành phần liên thông mạnh

Đề bài: http://vn.spoj.com/problems/TJALG/

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

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

int n, m, num[10005], low[10005],
cnt=0, connect[10005], numSCC=0;
vector<int> a[10005], S;

void dfs(int u) {
    low[u] = num[u] = cnt++;
    S.push_back(u);
    connect[u] = 1;
    for(int v : a[u]) {
        if (num[v] == -1) dfs(v);
        if (connect[v]) low[u] = min(low[u], low[v]);
    }

    if (num[u] == low[u]) {
        numSCC++;
        while(1) {
            int v = S.back(); S.pop_back();
            connect[v] = 0;
            if (u == v) break;
        }
    }
}

int main() {

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

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

    cout << numSCC;

    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ị.

– Có 2 mảng để đánh dấu, num[] và connect[].
+ Mảng num[] vừa để lưu thứ tự duyệt, vừa để kiểm tra xem một đỉnh u đã được duyệt đến hay chưa
+ Mảng connect[] dùng để kiểm tra xem đỉnh v có còn được “kết nối” trong đồ thị hay không ? Nếu phát hiện ra một thành phần liên thông mạnh, và một đỉnh v có trong thành phần liên thông mạnh đó, thì ta loại đỉnh v này ra khỏi đồ thị bằng câu lệnh connect[v] = 0, điều này là quan trọng vì để tránh gây ảnh hưởng đến việc nén mảng low[] của những đỉnh khác vẫn còn nằm trong đồ thị.

Happy coding

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

Dãy con liên tiếp có tổng lớn nhất

Đề bài: Cho dãy số A, tìm và in ra vị trí bắt đầu, kết thúc của dãy con liên tiếp có tổng lớn nhất; và tổng lớn nhất đó

Input:
5
1 2 3 4 -5

Output:
1 4 10

Code C++:
Độ phức tạp O(N)

#include <iostream>
#include <utility>
using namespace std;

/*---------------------------*/

int main() {
    
    int n; cin >> n;
    long long sum = 0;
    long long ans = 0;
    int tracki = 1;
    pair<int,int> resIndex;
    for(int i = 1; i <= n; i++) {
        int v;
        cin >> v;
            
        sum += v;
            
        if (ans < sum ||
            (ans == sum /* && i-tracki > resIndex.se - resIndex.fi) */)) {
                ans = sum;
                resIndex.first = tracki;
                resIndex.second = i;
            }
            
        if (sum < 0) {
            sum = 0;
            tracki = i + 1;
        }
            
    }
    
    if (ans <= 0) cout << "Bad input";
    else cout << resIndex.first << " " << resIndex.second << ' ' << ans;

    return 0;
}

Trie

Đề bài: http://www.spoj.com/problems/DICT/

Code C++:

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

struct node {
    bool w = false;
    int next[26];
};
node trie[700000];
int t = 0;
string p;
string rest;

void insert( const string & word ) {
    int node = 0;
    for(int i = 0; i < word.size(); i++) {
        int letter = (word[i] - 'a');
        trie[node].next[letter] = trie[node].next[letter] ? trie[node].next[letter] : ++t;
        node = trie[node].next[letter];
    }
    trie[node].w = true;
}

void dfs(int node) {
    if ( trie[node].w && rest.size() ) cout << p + rest << '\n';
    for(int i = 0; i < 26; i++) {
        if (trie[node].next[i]) {
            rest.push_back('a' + i);
            dfs( trie[node].next[i] );
            rest.pop_back();
        }
    }
}

void solve( const string & p ) {
    int node = 0;
    for(int i = 0; i < p.size(); i++) {
        int letter = (p[i] - 'a');
        if (trie[node].next[letter] == 0) {
            cout << "No match.\n";
            return;
        } else node = trie[node].next[letter];
    }
    rest.clear();
    dfs( node );
}

int main() {
    ios::sync_with_stdio(0);
    int n; cin >> n; cin.ignore(1);
    for(int i = 1; i <= n; i++) {
        string word; getline(cin, word);
        insert(word);
    }
    int q; cin >> q; cin.ignore(1);
    for(int i = 1; i <= q; i++) {
        getline(cin, p);
        cout << "Case #" << i << ":\n";
        solve( p );
    }
    
    return 0;
}

Độ phức tạp:
– Nếu có N words và độ dài mỗi word trung bình M thì Trie của N words này được xây dựng trong O(NM)
– Để xử lí một word có độ dài M trên xâu thì thông thường mất O(M)

Ghi chú:
– Thuật toán xây dựng Trie đơn giản, dễ nhớ, dễ hiểu
– Nếu có N words và độ dài mỗi word trung bình M thì Trie sẽ có tối đa N*M node
– Tuỳ vào bài toán mà chúng ta thêm thông tin cho node của cây Trie. Trong bài tập ở trên, ở mỗi node, chúng ta chỉ cần lưu chỉ số của node tiếp theo tương ứng với từng kí tự (cái này chắc chẳn phải có rồi) và biến w với ý nghĩa: word có được khi duyệt từ node 0 (root) đến node i nếu có trong từ điển thì Trie[i].w = true.

Happy coding,