โปรแกรม C++ ตรวจสอบว่ากองตัวอักษรสามารถว่างเปล่าได้หรือไม่

มีตัวอักษร 2n ตัว แต่ละตัวมีตัวเลข 1 ถึง n (แต่ละตัวเลขมี 2 ใบ) จัดเป็น m กอง (stacks) ต้องการว่างเปล่าทุกกองโดย: เลือก 2 กอง นำตัวอักษรบนสุดออกทั้งคู่ ต้องมีตัวเลขเท่ากัน ถ้าทำได้พิมพ์ true มิฉะนั้น false

ตัวอย่าง: n=3, m=2, stacks={{2,1,3},{2,1,3}} ผลลัพธ์: true (1) เพราะนำออกคู่ๆ ได้หมด

ขั้นตอนการแก้ปัญหา (Topological Sort / Graph)

1. สร้างกราฟ dp: จากแต่ละกอง ดูจากบนลงล่าง ถ้าตัวก่อนหน้า p อยู่เหนือตัวปัจจุบัน x ใส่ edge x → p (หมายความ x ต้องถูกนำออกก่อน p)
2. tvec[x] = indegree (จำนวนตัวที่บังคับให้ถูกนำออกก่อน x)
3. สำหรับแต่ละตัวเลข i = 1..n ทำ BFS/Topological: เริ่มจาก i ถ้า tvec[i]==0 และยังไม่ประมวลผล ให้ลด indegree ของเพื่อนบ้าน และ push เข้าคิว
4. ถ้าหลังจบ tvec ทุกตัวเป็น 0 → สำเร็จ (true) มิฉะนั้น false

ตัวอย่างโค้ด C++

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

bool solve(int n, int m, vector<vector<int>> stacks) {
    vector<vector<int>> dp(n + 1);
    vector<int> tvec(n + 1);
    for (int i = 0; i < m; i++) {
        int k = stacks[i].size();
        int p;
        for (int j = 0; j < k; j++) {
            if (j > 0) {
                dp[stacks[i][j]].push_back(p);
                tvec[p]++;
            }
            p = stacks[i][j];
        }
    }
    vector<bool> tp(n + 1);
    for (int i = 1; i <= n; i++) {
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            if (!tp[q.front()] && tvec[q.front()] == 0) {
                for (auto next : dp[q.front()]) {
                    tvec[next]--;
                    q.push(next);
                }
                tp[q.front()] = true;
            }
            q.pop();
        }
    }
    for (int i = 1; i <= n; i++)
        if (tvec[i] != 0) return false;
    return true;
}

int main() {
    int n = 3, m = 2;
    vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
    cout << solve(n, m, stacks);
    return 0;
}

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

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

Output: 1 (true)