Bài A

Thuật toán:

Chúng ta sẽ đến với 1 cấu trúc dữ liệu là bảng thưa

Gọi $trace[x][i]$ là cha của nút $x$ khi dfs từ $1$ và độ cao từ nó đến $x$ là $2^i$

Ví dụ $trace[x][0]$ là cha trực tiếp của đỉnh $x$ khi dfs từ $1$

Vậy chúng ta sẽ tìm $trace[x][i]$ như thế nào ?

Chúng ta thấy rằng $2^{i-1}+2^{i-1}=2^i$ $(1)$

Giả sử: Hiện tại ta có cha của $x$ mà có độ cao đến $x$ là $2^{i-1}$ và ta gọi nó là $par$ ($par=trace[x][i-1]$)

Áp dụng $(1)$ ta có thể tính $trace[x][i]$ bằng cách từ $par$ chúng ta. Tìm cha của $par$ mà cách $par$ 1 khoảng $2^{i-1}$ ( Tìm $trace[par][i-1]$ )

Khi đó $trace[par][i-1]$ chính là $trace[x][i]$ cần tìm:

Vì dồ thị chỉ có ${10}^5$ đỉnh thì khi đó trường hợp xấu nhất là đỉnh x cần đi qua hết ${10}^5$ đỉnh với mỗi $trace[x][i]$ thì $i$ lớn nhất là bao nhiêu $(2)$

Ta thấy, vì $trace[x][i]$ là đỉnh cha cách đỉnh x độ cao $2^i$ mà trong trường hợp xấu nhất như trên thì lúc này ta cần tìm k mà $2^k={10}^5$

Áp dụng Logarit thì ta có $k=lo{g}_2({10}^5)\Rightarrow k$ gần bằng $17$ nên chúng ta có thể suy ra đáp số $(2)$ cần tìm là $17$

CODE:

const int LOG=17;
void sprase_table()
{
    for(int i=1;i<=LOG;i++)
    {
        for(int node=1;node<=n;node++)
        {
            int par=trace[node][i-1];
            if(par!=-1)// Nếu x có nút cha cách nó độ cao 2 ^(i-1)
            {
                trace[node][i]=trace[par][i-1];
            }
        }
    }
}