Tìm thứ tự topo trong DAG

1. Tìm 1 thứ tự topo trong DAG sử dụng DFS

Mã giả C++:

vector<int> topo;
void dfs(int u) {
    visited[u] = true;
    for(int v : adj[u])
        if (!visited[v]) dfs(v);
    
    topo.push_back(u);
}

// topological ordering
for(int u = topo.size() - 1; u >= 0; u--)
    cout << u << ' ';

2. Tìm tất cả thứ tự topo trong DAG sử dụng backtracking

Happy coding,

Advertisements

Định chiều đồ thị

1. Bài toán định chiều đồ thị

– Cho đồ thị vô hướng, liên thông, thay mỗi cạnh bằng một cung định hướng để được một đồ thị có hướng, liên thông mạnh.

– Bài toán tổng quát: Với đồ thị vô hướng G = (V, E), hãy tìm cách thay mỗi cạnh của đồ thị bằng một cung định hướng để được đồ thị mới có ít thành phần liên thông mạnh nhất.

– Ứng dụng: Trong 1 hệ thống đường phố, có thể quy định các con đường là đường 1 chiều mà vẫn đảm bảo sự đi lại giữa 2 nút giao thông bất kì không ?

2. Các tính chất

– Đồ thị vô hướng, liên thông định chiều được chỉ khi:
+ Mỗi cạnh thuộc ít nhất một chu trình đơn
+ Suy ra mỗi cạnh đều không phải là cầu (bridge)

– Nếu đồ thị liên thông, mỗi cạnh thuộc ít nhất 1 chu trình đơn, thì thuật toán định chiều DFS (dưới đây) sẽ cho 1 đồ thị liên thông mạnh. Nếu không thì sẽ cho đồ thị định hướng ít thành phần liên thông mạnh nhất, cầu của đồ thị sẽ được định hướng thành cung nối giữa 2 thành phần liên thông mạnh.

3. Thuật toán và mã giả

– Thuật toán: định chiều đồ thị bằng DFS, trong quá trình duyệt DFS đỉnh u, xét các đỉnh v kề với nó:
+ Nếu v chưa thăm, định chiều cạnh u-v thành u->v và thăm v
+ Nếu v đã thăm, định chiều cạnh u-v thành u->v

– Mã giả:

void dfs(int u) {
    visit[u] = true;
    for(int v kề u) ) {
        Định chiều u-v thành u->v
        if (!visit[v]) dfs(v);
    }
}

// in main()
for(int u : Vertices)
    if (!visit[u]) dfs(u)

Trong lập trình, việc định chiều cạnh u-v thành cạnh u->v có thể được hiểu là loại đi chiều v->u

Happy coding

Kiểm tra chu trình trong đồ thị có hướng – cycle check

Ý tưởng:
– Sử dụng DFS
– Nếu đồ thị có hướng G có chu trình, thì sẽ tồn tại một đỉnh u thuộc G sao cho trong quá trình duyệt cây dfs gốc u, sẽ gặp lại chính đỉnh u này.
– Như vậy, với mỗi đỉnh u trong G, ta sẽ sử dụng một mảng đánh dấu visit[u] với ý nghĩa:
+ visit[u] = 0 – u chưa được thăm
+ visit[u] = 1 – u “đã được thăm” trong quá trình duyệt một cây DFS gốc nào đó.
+ visit[u] = 2 – u đã được thăm (quá trình duyệt cây DFS gốc u đã hoàn tất)
Xem code để hiểu rõ hơn

Code C++

cycle = false;

void dfs(int u) {
    visit[u] = 1; // đã được thăm trong quá trình duyệt cây dfs gốc u
    for(int v : a[u])
        if (visit[v] == 0) dfs(v);
        else if (visit[v] == 1) cycle = true; // nếu gặp 1 đỉnh v đã được thăm trong quá trình duyệt cây dfs gốc u, thì đồ thị có chu trình (chu trình này nằm trong cây dfs gốc u)

    visit[u] = 2; // kết thúc quá trình duyệt cây dfs gốc u, tất cả các đỉnh con trong cây này đều được cập nhập visit = 2
}

if (cycle) đồ thị G có chu trình

Lưu vết quá trình tìm kiếm bằng DFS

Đề bài: Cho đồ thị G, tập đỉnh V và tập cạnh E. Tìm đường đi từ đỉnh S đến đỉnh T và in ra các đỉnh và trạng thái của chúng:
– Trạng thái 1: Những đỉnh thuộc đường đi từ S -> T (BELONG_TO_PATH)
– Trạng thái 2: Những đỉnh không thuộc đường đi từ S -> T nhưng được viếng thăm (ATTEMPTED)
– Trạng thái 3: Những đỉnh không được viếng thăm (UNVISITED)

Mã giả C++:

bool dfs(int U) {
    // U is visited    
    if (U == T) return true;
    for(options V) {	
	if (V is unvisited && dfs(V)) { 
	    state[V] = BELONG_TO_PATH;
	    return true;
	}	
    }
    state[U] = ATTEMPTED;
    return false;
}

Modular multiplicative inverse – Tính nghịch đảo theo modulo

Nghịch đảo của a theo modulo m (Modular Multiplicative Inverse – MMI) là một số nguyên x sao cho:
a^{-1}\equiv x \enspace (\textrm{mod} \, m)

Tương đương với:
ax \equiv aa^{-1}\equiv 1 \enspace (\textrm{mod} \, m)

Nghịch đảo của a theo module m (là x) tồn tại chỉ khi a và m nguyên tố cùng nhau, tức là:
gcd(a,m)=1

Hãy xem xét một vài cách để tính MMI

1. Brute Force
Chúng ta có thể duyệt tìm số x sao cho:
ax \equiv 1 \enspace (\textrm{mod} \, m)

int divMod(int a, int m) {
    a %= m;
    for(int x = 1; x &lt; m; x++)
        if ((a*x) % m == 1) return x;
}

Độ phức tạp: O(M)

2. Sử dụng giải thuật Euclid mở rộng (Extended Euclidean Algorithm – EEA)
Chúng ta cần tìm số x sao cho a·x = 1 (mod m). Biểu thức này có thể viết lại thành a·x = 1 + m·y, tương đương với a·x – m·y = 1. Bởi vì x và y không nhất thiết phải là số dương, vì vậy chúng ta viết lại biểu thức ở dạng chuẩn:
a·x + m·y = 1

Trong số học, bổ đề Bézout phát biểu rằng: Nếu d là ước số chung lớn nhất của 2 số nguyên a, b; thì tồn tại 2 số nguyên x và y sao cho:
a·x + b·y = d
Và để tìm x, y; chúng ta có thể sử dụng EEA.

EEA là một sự mở rộng từ thuật toán Euclid. Bên cạnh việc tìm ước chung lớn nhất của 2 số a và b, EEA còn tìm ra 2 số x và y (thông thường 1 trong 2 số này sẽ âm) thoả mãn bổ đề Bézout: a·x + b·y = gcd(a, b).

EEA đặc biệt hữu dụng khi a và b là 2 số nguyên tố cùng nhau, khi đó x là nghịch đảo của a theo modulo b, và y là nghịch đảo của b theo modulo a (quy về bài toán hiện tại của chúng ta)

EEA kết hợp quá trình tìm GCD(a, b) trong thuật toán Euclid; đồng thời tìm thêm cặp số x, y thoả mãn bổ đề Lemma sử dụng công thức truy hồi:
1. Nếu a = 0, thuật toán kết thúc, trả về kết quả x = 0, y = 1 (Vì lúc này gcd(a, b) = b, vậy ta có ax + by = 0·0 + b·1 = b)
2. Ngược lại:
+ Tính thương q = b / a và số dư r = b % a
+ Đệ quy tìm cặp số x1, y1 sao cho a·x1 + r·y1 chia hết bởi a và r
+ Cuối cùng thuật toán trả về kết quả x = y1 – q · x1 và y = x1 (*)
(*)
Tại hàm đệ quy (a, b), ta cần tìm x, y sao cho a·x + b·y = gcd(a, b) = d.
Hàm này lại gọi đến hàm (b%a, a)
Tại hàm đệ quy (b%a, a), ta cần tìm x1, y1 sao cho:
(b%a)·x1 + a·y1 = gcd(b%a, a) = d.
Vậy ax + by = (b%a)x1 + ay1
Nếu chọn y = x1 (vì sao ? Chọn y khác thì sao ?) , tính toán ta có x = y1 – (b/a)·x1

Code C++:

int64_t extGcd(int64_t a, int64_t b, int64_t&amp; x, int64_t&amp; y) {
    if (!a) {
        x = 0;
        y = 1;
        return b;
    }
    int64_t x1, y1;
    int64_t d = extGcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

Độ phức tạp: O(log(max(a, b))

Như vậy để tính nghịch đảo của a theo modulo m, ta sử dụng hàm extGcd như sau:

int64_t x, y;
int64_t g = extGcd(a, m, x, y);
if (g != 1) // bad gcd
else // x là nghịch đảo của a theo modulo m

Tham khảo:
[1] http://vuontoanblog.blogspot.com/2012/11/Euclidean-algorithm1.html
[2] https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/
[3] http://vnoi.info/wiki/translate/he/Number-Theory

Happy coding,

Pillai’s arithmetical function – Thuật toán tính hàm Pillai

Trong lý thuyết số, hàm số Pillai được định nghĩa theo công thức sau:

P(n)=\sum_{k=1}^n\gcd(k,n)

Ta có thể viết lại như sau:
P(n) = \sum_{d\mid n} d cnt(d), với d là ước số của n và cnt(d) là số gặp (i,n) thoả mãn gcd(i,n) = d.

Theo tính chất của hàm gcd, nếu ta có gcd(a,b) = d thì gcd(a/d, b/d) = 1. Do đó công thức của hàm Pillai sẽ là:
P(n) = \sum_{d\mid n} d \phi(n/d), với \phiHàm phi Euler

Có thể tính được giá trị hàm Pillai của các số trong khoảng [1..N] bằng cách sàng Sieve tính trước Phi hàm Euler, sau đó sàng thêm một lần nữa để tính P(n).
Code
Độ phức tạp O(NlogN)

Nguồn tham khảo:

[1] https://en.wikipedia.org/wiki/Pillai’s_arithmetical_function

Happy coding

 

Euler’s totient function – Thuật toán tính Phi hàm Euler

Hàm số Euler của một số nguyên dương n (ký hiệu \phi(n)) là số các số i nguyên dương nhỏ hơn hoặc bằng n nguyên tố cùng nhau với n (GCD(i, n) = 1).

Một số công thức tính \phi(n):

  • \phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right), với p là ước nguyên tố của n
  • \phi(n)=\sum_{d\mid n} d \cdot \mu(n/d), với d là ước của n và \mu là hàm Mobius

Công thức đầu tiên cho ta ý tưởng về cách tính Phi hàm Euler bằng sàng nguyên tố Sieve với độ phức tạp O(NlogN):
Code

Các nguồn tham khảo:

[1] https://vi.wikipedia.org/wiki/Phi_hàm_Euler

Happy coding