Chương trình C++ tìm các đỉnh siêu trong đồ thị

Mô tả bài toán

Cho đồ thị vô hướng n đỉnh, mỗi đỉnh có giá trị x (từ 1 đến n). Đỉnh i gọi là "siêu" nếu trên đường đi ngắn nhất từ đỉnh 1 đến i không có đỉnh nào mang giá trị x trùng với đỉnh i. In ra tất cả các đỉnh siêu.

Ví dụ

n = 5, values = {1,2,2,1,3}, edges = {{1,2},{2,3},{2,3},{2,4},{4,5}}. Đầu ra: 1 3 4 5 (đỉnh 2 không phải siêu).

Thuật toán

1. DFS từ đỉnh 1, giữ mảng frq đếm tần suất giá trị x trên đường đi hiện tại.
2. Khi đến đỉnh j, nếu frq[vertexVal[j]] == 0 thì đánh dấu chk[j] = 1 (là đỉnh siêu).
3. Tăng frq, đệ quy các đỉnh con, sau đó giảm frq (backtrack).
4. Cuối cùng in các đỉnh có chk[i] != 0.

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

int n;
int vertexVal[100005], frq[100005], chk[100005];
vector<int> vcti[200005];

void dfs(int j, int k) {
    if(frq[vertexVal[j]] == 0) chk[j] = 1;
    frq[vertexVal[j]]++;
    for(auto a : vcti[j]) {
        if(a != k) dfs(a, j);
    }
    frq[vertexVal[j]]--;
}

void solve(int values[], vector<pair<int,int>> edges) {
    for(int i = 0; i < n; i++) vertexVal[i] = values[i];
    for(int i = 0; i < n; i++) {
        int a = edges[i].first, b = edges[i].second;
        vcti[a].push_back(b);
        vcti[b].push_back(a);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) if(chk[i]) cout << i << " ";
}

int main() {
    n = 5;
    int values[] = {1,2,2,1,3};
    vector<pair<int,int>> edges = {{1,2},{2,3},{2,3},{2,4},{4,5}};
    solve(values, edges);
    return 0;
}

Đầu vào / Đầu ra

Input: 5, {1, 2, 2, 1, 3}, {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}}

Output: 1 3 4 5