Thuật toán đồ thị

vector<bool> visited(n, false);
void dfs(int u, vector<vector<int>>& adj) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfs(v, adj);
}

vector<int> bfs(int src, vector<vector<int>>& adj) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    dist[src] = 0; q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v]==-1) { dist[v]=dist[u]+1; q.push(v); }
    }
    return dist;
}

vector<long long> dijkstra(int src, vector<vector<pair<int,int>>>& adj) {
    vector<long long> dist(adj.size(), LLONG_MAX);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> pq;
    dist[src]=0; pq.push({0,src});
    while (!pq.empty()) {
        auto [d,u]=pq.top(); pq.pop();
        if (d>dist[u]) continue;
        for (auto [w,v]:adj[u]) if (dist[u]+w<dist[v]) { dist[v]=dist[u]+w; pq.push({dist[v],v}); }
    }
    return dist;
}

vector<long long> dist(n, LLONG_MAX);
dist[src] = 0;
for (int i = 0; i < n-1; i++)
    for (auto [u,v,w] : edges)
        if (dist[u]!=LLONG_MAX && dist[u]+w<dist[v]) dist[v]=dist[u]+w;

for (int k=0; k<n; k++)
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);

sort(edges.begin(), edges.end());
DSU dsu(n);
long long cost = 0;
for (auto [w,u,v] : edges) if (dsu.unite(u,v)) cost += w;

vector<int> indegree(n, 0);
for (int u=0; u<n; u++) for (int v:adj[u]) indegree[v]++;
queue<int> q;
for (int i=0; i<n; i++) if (!indegree[i]) q.push(i);
vector<int> order;
while (!q.empty()) {
    int u=q.front(); q.pop(); order.push_back(u);
    for (int v:adj[u]) if (!--indegree[v]) q.push(v);
}