//bài toán: tìm đường đi ngắn nhất từ đỉnh Start đến tất cả các đỉnh còn lại, đồ thị vô hướng không trọng số
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 15;
 
vector<int> adj[MAXN];
bool visited[MAXN];
vector<int> dist(MAXN);
 
void bfs(int start) {
    queue<int> q;
 
    q.push(start);
    visited[start] = true;
    dist[start] = 0;
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
 
        cout << u << ", distance from startNode: "<< dist[u]<<endl;
 
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}
 
int main() {
    int n = 9, m; // n đỉnh m cạnh
    vector<pair<int,int>> edges = {{0,1},{0,2},{1,3},{1,4},{2,5},{2,6},{3,7},{4,8},{5,8},{6,9}};
    m = edges.size();
 
    for (int i = 0; i < m; i++) {
        int u, v;
        u = edges[i].first; v = edges[i].second;
        adj[u].push_back(v);
        adj[v].push_back(u); // bỏ dòng này nếu là đồ thị có hướng
    }
 
    int start = 0;
    bfs(start);
 
    return 0;
}

Ly9iw6BpIHRvw6FuOiB0w6xtIMSRxrDhu51uZyDEkWkgbmfhuq9uIG5o4bqldCB04burIMSR4buJbmggU3RhcnQgxJHhur9uIHThuqV0IGPhuqMgY8OhYyDEkeG7iW5oIGPDsm4gbOG6oWksIMSR4buTIHRo4buLIHbDtCBoxrDhu5tuZyBraMO0bmcgdHLhu41uZyBz4buRCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxNTsKCnZlY3RvcjxpbnQ+IGFkaltNQVhOXTsKYm9vbCB2aXNpdGVkW01BWE5dOwp2ZWN0b3I8aW50PiBkaXN0KE1BWE4pOwoKdm9pZCBiZnMoaW50IHN0YXJ0KSB7CiAgICBxdWV1ZTxpbnQ+IHE7CiAgICAKICAgIHEucHVzaChzdGFydCk7CiAgICB2aXNpdGVkW3N0YXJ0XSA9IHRydWU7CiAgICBkaXN0W3N0YXJ0XSA9IDA7CgogICAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgICAgICBpbnQgdSA9IHEuZnJvbnQoKTsKICAgICAgICBxLnBvcCgpOwoKICAgICAgICBjb3V0IDw8IHUgPDwgIiwgZGlzdGFuY2UgZnJvbSBzdGFydE5vZGU6ICI8PCBkaXN0W3VdPDxlbmRsOwoKICAgICAgICBmb3IgKGludCB2IDogYWRqW3VdKSB7CiAgICAgICAgICAgIGlmICghdmlzaXRlZFt2XSkgewogICAgICAgICAgICAgICAgdmlzaXRlZFt2XSA9IHRydWU7CiAgICAgICAgICAgICAgICBkaXN0W3ZdID0gZGlzdFt1XSArIDE7CiAgICAgICAgICAgICAgICBxLnB1c2godik7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW50IG4gPSA5LCBtOyAvLyBuIMSR4buJbmggbSBj4bqhbmgKICAgIHZlY3RvcjxwYWlyPGludCxpbnQ+PiBlZGdlcyA9IHt7MCwxfSx7MCwyfSx7MSwzfSx7MSw0fSx7Miw1fSx7Miw2fSx7Myw3fSx7NCw4fSx7NSw4fSx7Niw5fX07CiAgICBtID0gZWRnZXMuc2l6ZSgpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgaW50IHUsIHY7CiAgICAgICAgdSA9IGVkZ2VzW2ldLmZpcnN0OyB2ID0gZWRnZXNbaV0uc2Vjb25kOwogICAgICAgIGFkalt1XS5wdXNoX2JhY2sodik7CiAgICAgICAgYWRqW3ZdLnB1c2hfYmFjayh1KTsgLy8gYuG7jyBkw7JuZyBuw6B5IG7hur91IGzDoCDEkeG7kyB0aOG7iyBjw7MgaMaw4bubbmcKICAgIH0KCiAgICBpbnQgc3RhcnQgPSAwOwogICAgYmZzKHN0YXJ0KTsKCiAgICByZXR1cm4gMDsKfQ==