Tìm tất cả đỉnh có thể đến từ mọi đỉnh trong tập cho trước trong C++

Cho đồ thị vô hướng và tập đỉnh, tìm tất cả đỉnh có thể đến từ mỗi đỉnh trong tập cho trước.

Ví dụ: với đồ thị như hình, kết quả là [1,2,3] và [4,5] vì đây là hai thành phần liên thông.

Các bước:

• nodes = số đỉnh đồ thị
• Mảng visited[nodes+1] = 0
• Map m
• comp_sum = 0
• Với i từ 0 đến n-1: u = arr[i]; nếu visited[u] false thì comp_sum++, m[visited[u]] = BFS từ u tính comp_sum; in duyệt m[visited[u]]

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Graph{
public:
    int nodes;
    list<int> *adj_list;
    Graph(int);
    void insert_edge(int, int);
    vector<int> BFS(int, int, int []);
};
Graph::Graph(int nodes) {
    this->nodes = nodes;
    adj_list = new list<int>[nodes+1];
}
void Graph::insert_edge(int u, int v) {
    adj_list[u].push_back(v);
    adj_list[v].push_back(u);
}
vector<int> Graph::BFS(int comp_sum, int src,int visited[]){
    queue<int> queue;
    queue.push(src);
    visited[src] = comp_sum;
    vector<int> reachableNodes;
    while(!queue.empty()) {
        int u = queue.front(); queue.pop();
        reachableNodes.push_back(u);
        for (auto itr = adj_list[u].begin(); itr != adj_list[u].end(); itr++) {
            if (!visited[*itr]) {
                visited[*itr] = comp_sum;
                queue.push(*itr);
            }
        }
    }
    return reachableNodes;
}
void displayReachableNodes(int n, unordered_map <int, vector<int> > m) {
    vector<int> temp = m[n];
    for (int i=0; i<temp.size(); i++) cout << temp[i] << " ";
    cout << endl;
}
void get_all_reachable(Graph g, int arr[], int n) {
    int nodes = g.nodes;
    int visited[nodes+1];
    memset(visited, 0, sizeof(visited));
    unordered_map <int, vector<int> > m;
    int comp_sum = 0;
    for (int i = 0 ; i < n ; i++) {
        int u = arr[i];
        if (!visited[u]) {
            comp_sum++;
            m[visited[u]] = g.BFS(comp_sum, u, visited);
        }
        cout << "Các đỉnh có thể đến từ " << u << " là\n";
        displayReachableNodes(visited[u], m);
    }
}
int main() {
    int nodes = 5;
    Graph g(nodes);
    g.insert_edge(1, 2);
    g.insert_edge(2, 3);
    g.insert_edge(4, 5);
    int arr[] = {2, 4, 1};
    int n = sizeof(arr)/sizeof(int);
    get_all_reachable(g, arr, n);
}

Đầu vào

g.insert_edge(1, 2); g.insert_edge(2, 3); g.insert_edge(4, 5);

Đầu ra

Các đỉnh có thể đến từ 2 là 2 1 3
Các đỉnh có thể đến từ 4 là 4 5
Các đỉnh có thể đến từ 1 là 2 1 3