Print matrix in spiral order

Input:

3

Output:

1 2 3
8 9 4
7 6 5

Code C++:

void spiral_matrix(const int n) {
    vector<vector<int>> a;
    a.assign(n+1, vector<int>(n+1,0));
    
    int cnt = 0;
    int i = 1, j = 1;
    
    while(cnt < n*n) {
        // left to right
        while(j <= n && a[i][j] == 0) {
            a[i][j] = ++cnt;
            j++;
        }
        j--; i++;
        
        // top to bot
        while(i <= n && a[i][j] == 0) {
            a[i][j] = ++cnt;
            i++;
        }
        i--; j--;
        
        // right to left
        while(j >= 1 && a[i][j] == 0) {
            a[i][j] = ++cnt;
            j--;
        }
        j++; i--;
        
        // bot to top
        while(i >= 1 && a[i][j] == 0) {
            a[i][j] = ++cnt;
            i--;
        }
        i++; j++;
    }
    
    
    
    // print result
    for(int i = 1; i < (int)a.size(); i++) {
        for(int j = 1; j < (int)a[1].size(); j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}

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,

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;
}