โปรแกรม C++ หาจุดยอด Super Vertices ในกราฟ

กำหนดกราฟที่มี n จุดยอด (หมายเลข 1 ถึง n) เชื่อมต่อด้วยเส้นขอบในอาร์เรย์ edges แต่ละจุดยอดมีค่า x (1 ถึง n) ในอาร์เรย์ values จุดยอด i จะเป็น "Super Vertex" ก็ต่อเมื่อเส้นทางสั้นที่สุดจากจุดยอด 1 ไปยัง i ไม่มีจุดยอดใดที่มีค่า x เท่ากับจุดยอด i ต้องการพิมพ์จุดยอดทั้งหมดที่เป็น Super Vertex

ตัวอย่าง: n = 5, values = {1, 2, 2, 1, 3}, edges = {{1, 2}, {2, 3}, {2, 3}, {2, 4}, {4, 5}} ผลลัพธ์: 1 3 4 5 (จุดยอด 2 ไม่ผ่านเกณฑ์)

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์ vertexVal, frq, chk ขนาด 100005 และ vcti ขนาด 200005
2. ฟังก์ชัน dfs(j, k):
   • ถ้า frq[vertexVal[j]] == 0 ตั้ง chk[j] = 1
   • เพิ่ม frq[vertexVal[j]]++
   • วนลูปเพื่อนบ้าน a ของ j ถ้า a != k เรียก dfs(a, j)
   • ลด frq[vertexVal[j]]--
3. เตรียมข้อมูล: กำหนด vertexVal จาก values สร้างกราฟจาก edges
4. เรียก dfs(1, 0)
5. พิมพ์จุดยอด i ที่ chk[i] != 0

ตัวอย่างโค้ด 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;
        int 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 << endl;
    }
}

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;
}

อินพุต / เอาต์พุต

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

Output: 1 3 4 5