## Nói qua về đồ thị
- Đồ thị là tập hợp gồm cách đỉnh và các đỉnh được nối với nhau bằng các cạnh
- 2 loại cạnh
- Cạnh 1 chiều (cạnh u v là nối đỉnh u với đỉnh v và chỉ có thể đi từ u qua v)
- Canh 2 chiều (vô hướng) (cạnh u v mối đỉnh và đỉnh v và có thể đi được 2 hướng là từ u qua v và từ v qua u)
- 2 đỉnh kề nhau là 2 đỉnh có cạnh nối trực tiếp với nhau

3 2
1 2
2 3

Đỉnh 1 và 2 là 2 đỉnh kề nhau vài có cạnh nối trực tiếp là 1 2
Tương tự đỉnh 2 3 cũng là 2 đỉnh kề nhau
1 3 không phải là 2 đỉnh kề nhau bởi vì nó không có cạnh nối trực tiếp

- Đa đồ thị: (lưu ý với cái này nhiều thuật toán sẽ bị sai đối với đa đồ thị)
- Sẽ có 1 đỉnh có cạnh nối với đỉnh đó (khuyên)
- Với 2 đỉnh u v có nhiều hơn 1 cạnh nối giữa 2 đỉnh đó
- có thêm 2 trường hợp này gọi là đa đồ thị
- Đồ thị liên thông
- Là đồ thị mà từ 1 đỉnh bất kì có thể đến được mọi đỉnh khác trong đồ thị thì đồ thị đó gọi là đồ thị liên thông
- Thành phần liên thông
- Trong 1 thành phần liên thông thì 2 đỉnh bất kì luôn có thể đi đến được nhau từ các cạnh (có thể nói là thành phần liên thông đó là đồ thị liên thông)

- Chu trình là khi mình xuất phát từ 1 đỉnh đi qua ít nhất 1 cạnh và không đi lại cạnh đã đi mà quay về được đỉnh đó thì gọi cái đường đi đó là chu trình
- DAG là đồ thị có hướng và không có chu trình (sau này mình sẽ có nhiều dạng bài toán về cái DAG như quay hoạch động trên DAG)

### Từ đồ thị đến cây
- Một đồ thị được gọi là cây nếu thỏa mãn 2 điều kiện sau:(điều kiện ở đồ thị vô hướng)
- Đồ thị đó phải liên thông ( 2 đỉnh bất kì luôn đi được đến nhau)
- Có đúng n - 1 cạnh
=> đồ thị đó được gọi là cây
- cây có rất nhiều thuật toán và bài toán nó còn nhiều thuật toán hơn cả đồ thị bình thường
- Sau này sẽ có rất nhiều bài toán liên quan đến cây

## Cách lưu cạch của đồ thị
- Cách 1:
- Sử dụng danh sách kề:

   vector <int> adj[N];
   // adj[u] là danh sách các đỉnh kề của u

   int n , m;
   cin >> n >> m; // m số cạnh n là số đỉnh 
   for (int i = 1 ; i <= m ; i++){
       int x , y;
       cin >> x >> y; // đồ thị vô hướng 
       // vì x và y có cạnh nối trực tiếp nên x và y kề nhau nên mình cho nó vào danh sách kề của nhau
       adj[x].push_back(y);
       adj[y].push_back(x);
   }

- Một cách phổ biến để lưu lại các đỉnh kề của đồ thị
- Cách thứ 2 là ma trận kề:
- Đồ thị có n đỉnh thì mình xây dựng ma trận adj $n \cdot n$
- Nếu đỉnh u và v kề nhau thì adj[u][v] = 1; và adj[v][u] = 1 (đối với vô hướng);
- Nếu nó là đồ thị có hướng thì chỉ thêm adj[u][v] =1

    int adj[N][N];
    memset(adj,0,sizeof(adj));
    int n , m;
    for (int i = 1 ; i <= m ; i++){
        int x , y;
        cin >> x >> y; // đồ thị vô hướng
        adj[x][y] = 1;
        adj[y][x] = 1;
    }

- Cách này ít phổ biến hơn bởi vì nó tốn bộ nhớ hơn rất nhiều và duyệt mỗi lần phải tốn O(n) thay vì là tốn số đỉnh kề như cách trên
## Thuật toán DFS(depth first search) (tìm kiếm theo chiều sâu)

- Nhắc lại về stack: có thể hiểu như sau nó là cái thùng có đáy mình bỏ các hộp vào thùng từ phía trên và lấy các hộp ra từ phía trên
- Thuật DFS sẽ được mô tả như sau:
- 1: chọn đỉnh đầu tiên để thưc hiện thuật toán ví dụ đỉnh đầu tiên là root
- 2: Sau đó thêm root vào stack
- 3: Nếu stack còn trống thì thực hiện tiếp không thì đến bước 7
- 4: lấy đỉnh top ra khỏi stack (cái đỉnh cho vào cuối cùng hay còn nói là muộn nhất) và đánh dấu đã thăm đỉnh này
- 5: duyệt qua các đỉnh kề với đỉnh vừa lấy ra nếu như đã thăm rồi thì bỏ qua không thì mình thêm nó vào stack
- 6: quay lại bước 3
- 7: kết thúc thuật toán

void dfs(int root){
   int visited[N]; // mảng kiểm tra xem các đỉnh đã thăm hay chưa nếu bằng 0 thì chưa thăm ngược lại thì thăm rồi 
    vector <int> a[N]; // dach sách kề 
    memset(visited,0,sizeof(visited));
    stack <int> st;
    st.push(root);
    while (!st.emtpy()){
        int u = st.top();
        st.pop(); // xóa đỉnh top ra khỏi stack
        visited[u] = 1;
        for (int v : a[u]) // duyệt qua các đỉnh kề 
            if (visited[v] == 0) // chưa thăm đỉnh này trước đó
                st.push(v);
    }
}

#### Cách cài thứ 2:
- Sử dụng đệ quy (khó tưởng tượng hơn cách 1 nhưng sẽ áp dụng nhiều hơn) khuyến khích cài theo cách này
- Hầu như ai cũng cài theo cách này
- Mình thay while bằng đệ quy và không push vào stack vì mình có thể quay lại các bước trước do sử dụng đệ quy

 int visited[N]; // mảng kiểm tra xem các đỉnh đã thăm hay chưa nếu bằng 0 thì chưa thăm ngược lại thì thăm rồi 
vector <int> a[N]; // dach sách kề 

void dfs(int u){
    visited[u] = 1;
    for (int v : a[u])
        if (visited[v] == 0) // chưa thăm thì thăm luôn không cần bỏ vào stack làm gì cả
             dfs(v);
}

int main(){
    memset(visited,0,sizeof(visited));
    dfs(1);
}

## Ứng dụng vào code
- Dùng để đếm số đỉnh trong 1 thành phần liên thông
- Dùng để đếm số thành phần liên thông trong một đồ thị
- Dùng để thực hiện các thuật toán trên cây (hầu hết cách thuật toán trên cây đề sử dụng DFS)

## Bài 1:
- Mình sẽ duyệt các đỉnh từ 1 đến n và kiểm tra đỉnh đó đã thăm hay hay chưa nếu chưa thì mình sẽ DFS đỉnh đó và tăng đếm lên 1
- cuối cùng là in ra đếm
- Tại sao vậy lại đúng bởi vì
- Khi mà dfs 1 đỉnh trong 1 thành phần liên thông thì sẽ duyệt qua hết các đỉnh còn lại trong thành phần liên thông đó

 int visited[N]; // mảng kiểm tra xem các đỉnh đã thăm hay chưa nếu bằng 0 thì chưa thăm ngược lại thì thăm rồi 
vector <int> a[N]; // dach sách kề 

void dfs(int u){
    visited[u] = 1;
    for (int v : a[u])
        if (visited[v] == 0) // chưa thăm thì thăm luôn không cần bỏ vào stack làm gì cả
             dfs(v);
}

int main(){
    memset(visited,0,sizeof(visited));
    
    int count = 0;
    for (int i = 1 ; i <= n ; i++)
        if (!visited[i]){
            count++;
            dfs(i);
        }
    
    cout << count;
}

## Thuật toán BFS (thuật toán tìm kiếm theo chiều rộng)
- Cách cài thì nó cũng tương với thuật toán DFS chỉ cần đổi stack thành queue là được
- có thể hiểu thuật toán này hoạt động kiểu :
- Khi xuất phát từ đỉnh u thì đỉnh nào gần với đỉnh u hơn thì thăm trước rồi cách đỉnh xa hơn thì thăm sau
- Nãy có nói về queue thì đỉnh bỏ vào đầu tiên thì lấy ra đầu tiền
- Bởi vì đỉnh bỏ vào càng sớm (càng đầu tiên thì càng gần với đỉnh u hơn)
- Thuật toán này còn gọi là thuật toán loang vì nhìn cách hoạt động của nó nhưng sự loang đi của nước ...

void bfs(){
    vector <int> adj[N];
    int distants[N]; // thay vì mảng thăm distants u = -1 thì đỉnh đó chưa thăm ngược lại thì đã thăm khi mình dùng mảng distants thì mình sẽ biêts được khoảng cách ngắn nhất từ đỉnh u đến đỉnh root.

    queue <int> q;
    q.push(root);
    while (!q.empty()){
        int u = q.front(); // thay vì lấy top thì lấy front là cái bỏ vào sớm nhất 
        for (int v : a[u])
            if (distans[v] == -1){
                distans[v] = distans[u] + 1;
                q.push(v);
            }
    }
}

- Thuật toán này không làm được bằng đệ quy
#### 2 thuật toán này đều có độ phức tạp là O(n);

### Ứng dụng:
- Dùng để tìm đường đi ngắn nhất từ đủ root cho đến mọi đỉnh còn lại áp dụng cho đồ thị không có trọng số hoặc tất cả trọng số bằng 1
- Ứng dụng vào đời sống như code mấy game minesweeper

## Bài 2:

void bfs(){
    vector <int> adj[N];
    int distants[N]; // thay vì mảng thăm distants u = -1 thì đỉnh đó chưa thăm ngược lại thì đã thăm khi mình dùng mảng distants thì mình sẽ biêts được khoảng cách ngắn nhất từ đỉnh u đến đỉnh root.

    queue <int> q;
    q.push(s);
    while (!q.empty()){
        int u = q.front(); // thay vì lấy top thì lấy front là cái bỏ vào sớm nhất 
        for (int v : a[u])
            if (distants[v] == -1){
                distants[v] = distants[u] + 1;
                q.push(v);
            }
    }
    
    
    vector <pair<int,int> > output;
    for (int i = 1 ; i <= n ; i++)
        output.push_back(pair<int,int>(distants[i],i);
                         
    sort(All(output));
    for (pair <int,int> v : output)
        cout << v.second << " " << v.first << "\n";
}

## Bài 3:
- Nhận thấy đề cạnh không có trọng số và đường đi ngăn nhất từ s đến t
-> sử dụng bfs từ đỉnh s sau đó in ra distants[t] là biết được độ dài
- cần phải in ra đường đi
- thêm một mảng trace[u] với ý nghĩa là đỉnh mà mình thăm trước đỉnh u và nối distanst[u] = distanst[trace[u]] + 1;

void bfs(int s , int t){
    vector <int> adj[N];
    int distants[N]; // thay vì mảng thăm distants u = -1 thì đỉnh đó chưa thăm ngược lại thì đã thăm khi mình dùng mảng distants thì mình sẽ biêts được khoảng cách ngắn nhất từ đỉnh u đến đỉnh root.
    int trace[N];
    trace[s] = 0;

    queue <int> q;
    q.push(s);
    while (!q.empty()){
        int u = q.front(); // thay vì lấy top thì lấy front là cái bỏ vào sớm nhất 
        for (int v : a[u])
            if (distants[v] == -1){
                trace[v] = u;
                distants[v] = distants[u] + 1;
                q.push(v);
            }
    }
    
     dequy(t);
    
    vector <int> p;
    while (trace[t] != s){
        p.push_back(t);
        t = trace[t];
    }
    
    p.push_back(s);
    
    // đảo vector lại 
    for (ỉnt v : p) cout << v << "\n";
    
    
    

Đây là cách làm của người bỉnh thường

    vector <int> p;
    while (trace[t] != s){
        p.push_back(t);
        t = trace[t];
    }
    
    p.push_back(s);
    
    // đảo vector lại 
    for (ỉnt v : p) cout << v << "\n";

Mình có thể thông minh hơn một chút là thay vì dùng vector và đảo lằng nhằng thì mình dùng đệ quy

void dequy(int u){
    if (u == 0) return ;
    else dequy(trace[u]);
    cout << u << " ";
    // đúng thứ tự luôn không cần phải đảo 
}

## Bài 4:
- Đây là DAG và thuật toán mình áp dụng được cho bài này quy hoạch động trên DAG
- $dp_{u}$ là đường đi dài nhất mà u có thể đi được
- Vì sao không phải DAG thì thuật toán này sai:
- Nếu không phải DAG thì:
- Đồ thị vô hướng
- Đồ thị có hướng và có chu trình
- vì sao $dp_{u}$ lại hoạt động bởi vì khi mỗi lần mình gọi hàm DFS(u) thi luôn chỉ có một đường đi dài nhất mà đáp án không bị thay qua nhiều lần gọi và nó sẽ không lên đỉnh mà mình gọi nó

// ban đầu mảng dp = - 1; là chưa gọi dfs lần nào 
int dfs(int u){
    int &res = dp[u];
    if (res != -1) return res; // đã duyệt 1 lần rồi thì không duyệt lại nữa tại vì mỗi lần duyệt đều có đáp án giống nhau nên mình thêm nhớ được
    res = 0; // ban đâuf đương đi dài nhất là 0 
    for (int v: a[u])
        res = max(res,dfs(v) + 1); // cộng thêm cạnh nối từ đỉnh v  dến đỉnh u 
    return res;
}


int main(){
    memset(dp,-1,sizeof(dp));
    // hàm memset chỉ áp dụng được với ox3f và -1 và 0. không áp dụng được với những số khác ví dụ nhu 1
    for (int i = 1 ; i <= n ; i++)
        res =max (res,dfs(i));
    cout << res;
}

- cách em nguyên cứu thử tại sao nó lại hoạt động đúng

## Bài 5:
- Nếu các em học dsu trước thì tư duy dễ hơn hoặc không cần thiết cũng được
- Khi mình gộp 2 set lại làm một mà mình chọn set nhỏ hơn vào set lớn hơn thì mình chỉ có tối đa n*log lần thực hiện chuyển số từ set này qua set kia
- Tại sao lại vậy thì trường hợp xấu nhất là 2 set có độ dài bằng nhau: để 2 set có độ dài bằng nhau thì đó là cây nhị phân thì cây nhị phân nó gộp kiểu là có tối đa n*log thao tác

- không ném 2 set vào 1 set mới vì kiểu đó tốn tận n^2

## Bài 14

- Nhìn vào : m dòng tiếp theo, dòng thứ i gồm hai số nguyên a và b (1 ≤ a, b ≤ n) − con đường nối ngôi nhà a với ngôi nhà b. Dữ liệu luôn đảm bảo không tồn tại cặp chỉ số (i, j) nào mà cả hai cô gái i và j đều có thể đi đến nhà của nhau
-> Đây là DAG
- Bài toán đếm thì đường sẽ sử dụng dp đối với bài toán này thì mình dùng quy hoạch động trên DAG

- Để quy hoạch động:
- gọi dp[u] là số cách đi từ đỉnh 1 đến đỉnh u
- để dp[u] đủ trạng thái thì mình cần phải cập nhật trạng thái của tất cả đỉnh nối đến u
- sau khi đỉnh u đỉ trạng thái (dp[u] đúng) thì mình cập nhật dp[u] cho các đỉnh mà u nối đến

    queue <int> p;
    int check[N];
    cin >> n >> m;
    for (int i = 1; i <= m ; i++){
        int x , y;
        cin >> x >> y;
        check[y]++; 
        a[x].push_back(y);
    }

// check[u] = số đỉnh nối đến u 
    memset(dp,0,sizeof(dp));
    for (int i = 1 ; i <= n ; i++)
        if (check[i] == 0) p.push(i);
// không có cạnh nào nối với đỉnh i thì push vào p
// quy hoạch động theo thứ tự của bfs
// hầu hết các bài dag đều quy hoạch động theo thứ tự này 
    dp[1] = 1;
    while (!p.empty()){
        int u = p.front();
        // khi 1 đỉnh đã được push vào queue thì nó luôn đủ trạng thái 
        p.pop();
        for (int v : a[u]){
            add(dp[v],dp[u]);
            check[v]--;
            // mình đã đi qua cạnh u v rồi thì bỏ cạch đó ra nên check[v] phải trừ đi 1 
            
            if (check[v] == 0) // nếu check[v] = 0 thì đỉnh v đã được cập nhật đủ trạng thái cho nên mình push nó vào queue
                p.push(v);
        }
        
    }

    cout << dp[n];

## Bài 15
### Tóm tắt đề:
- cho một đồ thị vô hướng gồm n đỉnh và m cạnh tìm cách thêm 1 cạnh sao cho thành phần liên thông lớn nhất có nhiều đỉnh nhất
- Áp dụng thuật toán đếm thành phần liên thông
- Trước a có dạy 2 thuật để đến số thành phần liên thông DFS và BFS
- Mình muốn thêm cạnh để thành phần liên thông to nhất là có nhiều đỉnh nhất dễ đàng nhận thấy là mình cần nối 2 thành phần liên thông lớn nhất vào với nhau là xong

int cnt = 0;
void dfs(int u){
    visit[u] = 1;
    cnt++;
    for (int v : a[u])
        if (!visit[v]) dfs(v); 
}

int main(){
    
    int Max = 0;
    int res = 0;
    for (int i = 1 ; i <= n ; i++)
        if (!visit[i]){
            cnt = 0;
            dfs(i);
            res = max(res,Max + cnt);
            Max = max(Max,cnt);
        }
    
    cout << res << "\n";
    return 0;
}

- Nối thành phần liên thông chứa 1 và 1 thành phần liên thông khác sau cho số đỉnh là lớn nhất

int cnt = 0;
void dfs(int u){
    visit[u] = 1;
    cnt++;
    for (int v : a[u])
        if (!visit[v]) dfs(v); 
}

int main(){
    
    int countone = 0;
    int res = 0;
    
    dfs(1);
    countone = cnt;
    
    for (int i = 1 ; i <= n ; i++)
        if (!visit[i]){
            cnt = 0;
            dfs(i);
            res = max(res,countone + cnt);
        }
    
    cout << res << "\n";
    return 0;
}

## Bài 16:
### Đề:
- Yêu cầu tìm đường kính của cây
- Định nghĩa: đường kính của cây là đường dài nhất của 2 đỉnh trong cây
### Giải:
- Có rất nhiều cách để tìm đường kính của cây
- Sẽ có 2 cạch được nêu ở đây:
#### Cách thứ nhất:
- Mình dfs từ 1 đỉnh bất kì và tìm đỉnh xa với nó nhất và gọi nó là u
- Tiếp theo mình dfs từ đỉnh u và tìm ra đỉnh xa với nó nhất gọi là đỉnh v
- koảng cách của 2 đỉnh u và v là đường kính của cây
#### Cách thứ 2:
- Quy hoạch động trên cây (đơn giản):
- Cách này áp dụng nhiều cho các bài quy hoạch động trên cây
- Cách làm:
+ Chọn một đỉnh bất kì làm gốc, thường thì một cây luôn có 1 cái gốc thường sẽ chọn đỉnh 1 làm gốc
+ mình sẽ duyệt theo thứ tự dfs từ đỉnh gốc
+ f[u] là đường đi dài nhất từ đỉnh u đến con của nó
+ g[u] là đường đi dài nhì từ đỉnh u đến các con của nó (đường f[u] và g[u] chỉ được trùng nhau điểm u, khi vẽ cái đường từ u đến con thì nó chỉ được trung nhau đúng điểm u thôi)

void dfs(int u,int par){
    f[u] = 0;
    g[u] = 0;
    for (int v : a[u]) // duyệt qua các con trực tiếp của nó
        if (v != par){
            dfs(v,u);
           // đã duyệt xong đỉnh v
            //đây là cái khúc đỉnh v lên lại u
            // vì v đã duyệt qua rồi nên mình có được f[v] và g[v];
            //để cập nhật từ đỉnh v cho đỉnh u để tìm đường đi dài nhất đến con của u 
            int dis = f[v] + 1;
            // đường đi dài nhất từ u đến các con của đỉnh v ,bởi vidf trong 1 con của v chỉ được chọn đúng 1 đường cho nên minh luôn chọn đường đi dài nhất vì nó luôn tối ưu hơn 
            if (dis > f[u]){
                g[u] = f[u] // cập nhẩt đường dài nhất trước đó cho g[u] 
                f[u] = dis;
            }
            else if (dis > g[u]){
                g[u] = dis;
            }
        }
    
    res = max(res,g[u] + f[u]);
}

cout << res;

// áp dụng cho quy hoạch động trên cây.

## Cấu trúc dữ liệu mới:
- nó khá là dễ hiểu:
### Cấu trúc dữ liệu: Disjoinssets
- Thuật toán áp dụng cho độ thị vô hướng
- Mô tả về nó : tìm một cây khung bất kì của đồ thị có thể hiểu là cho một đồ thị n đỉnh và m cạnh cần chọn ra các cạnh bất kí sao cho đồ thị còn lại (những cạnh được chọn) không tồn tại chu trình.
- Nó chỉ có thể là tập hợp các cây hoặc là đúng 1 cái cây.
- Mình sẽ có:
- Mình sẽ duyệt tập cạnh của đồ thị và xử lý
- Với mỗi thành phần liên thông thì mình sẽ có một đỉnh làm đỉnh gốc chỉ duy nhất một đỉnh làm đỉnh gốc
- Các đỉnh có trace[u] giống nhau thì sẽ chung một thành phần liên thông

    trace(u); //là đỉnh gốc (đỉnh dại diện cho đỉnh u) của đỉnh u trong thành phần liên thông chứa u
    
// cách trace đỉnh u 
int trace(int u){
    if (u != trac[u]) return trac[u] = trace(trac[u]);
    return u;
}

bool join(int u, int v){
    int u = trace(u); // tìm đỉnh gốc của u 
    int v = trace(v); // tìm đỉnh gốc của v 
    if (u == v) // chứng tỏ 2 cái này cùng gốc => nó chung 1 thành phần liên thông nếu như mình nối 2 đỉnh đó vào thì sẽ tồn tại chu trình 
        return false; // không nối được 
    // khi mà chúng khác gốc với nhau thì mình nối 2 gốc lại 
    trac[u] = v; // hoặc trac[v] = u đều được 
    return true;//nối được 2 cạnh với nhau
}

### Thuật toán tim cây khung nhỏ nhất
#### Cây khung nhỏ nhất của một đồ thị vô hướng liên thông là tìm ra một cái cây của đồ thị đó sao cho tổng trọng số của các cạnh là nhỏ nhất.
#### Cách làm:
- Mình chỉ cần sort cạnh trọng số tăng dần và duyệt từ hết các cạnh đó và nối chúng lại bằng disjoinssets (dùng disjoinssets để kiểm tra xem 2 đỉnh u v có chung thành phần liên thông hay không.

struct eg{
    int u, v, w;
    eg(){}
    eg(int u, int v, int w): u(u), v(v), w(w) {}
};

bool cmp(eg x, eg y){
    return x.w < y.w; // ham cmp để sort theo trọng số cạnh
}

eg canh[N];

int trace(int u){
    if (u != trac[u]) return trac[u] = trace(trac[u]);
    return u;
}

bool join(int u, int v){
    int u = trace(u); // tìm đỉnh gốc của u 
    int v = trace(v); // tìm đỉnh gốc của v 
    if (u == v) // chứng tỏ 2 cái này cùng gốc => nó chung 1 thành phần liên thông nếu như mình nối 2 đỉnh đó vào thì sẽ tồn tại chu trình 
        return false; // không nối được 
    // khi mà chúng khác gốc với nhau thì mình nối 2 gốc lại 
    trac[u] = v; // hoặc trac[v] = u đều được 
    return true;//nối được 2 cạnh với nhau
}

void main(){
    cin >> n >> m;
    for (int i = 1 ; i <= m ; i++){
        int x , y , w;
        cin >> x >> y >> w;
        canh[i] = eg(x,y,w);
       //  eg(int u, int v, int w): u(u), v(v), w(w) {}
    }
    
    for (int i = 1 ; i <= n ; i++) trac[i] = i; // cho đỉnh u có đỉnh gốc là chính nó 
    
    sort(canh + 1,canh + m + 1,cmp);
    int res = 0;
    for (int i = 1 ; i <= m ; i++)
        if (join(canh[i].u,canh[i].v)){
            res += canh[i].w;
        }
    
    cout << res << "\n"; // tông trọng số của cây khung nhỏ nhất 
}

## Bài 20