Chương trình C++ kiểm tra có thể làm rỗng các ngăn xếp chữ cái không

Mô tả bài toán

Có 2n chữ cái, mỗi số 1..n xuất hiện đúng 2 lần. Chúng được xếp thành m ngăn xếp. Mỗi phép toán: chọn 2 ngăn xếp, lấy chữ cái đỉnh của cả hai, yêu cầu cùng số. Xác định có thể làm rỗng tất cả ngăn xếp không.

Ví dụ

n=3,m=2, stacks={{2,1,3},{2,1,3}}. Đầu ra: true (1).

Thuật toán (Topological sort trên đồ thị phụ thuộc)

1. Xây đồ thị: nếu trong một ngăn xếp, chữ cái p nằm ngay trên → thêm cạnh (phải lấy p trước mới lấy được ).
2. tvec[x] = bậc vào của đỉnh .
3. Với mỗi đỉnh , nếu tvec[i]==0 và chưa xử lý, BFS: giảm bậc vào của các đỉnh kề, đẩy vào hàng đợi.
4. Nếu cuối cùng mọi tvec[i]==0 → true, ngược lại false.

Đoạn mã 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;i0) {
                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()) {
            int u=q.front(); q.pop();
            if(!tp[u] && tvec[u]==0) {
                for(int nxt: dp[u]) {
                    tvec[nxt]--;
                    q.push(nxt);
                }
                tp[u]=true;
            }
        }
    }
    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;
}

Đầu vào / Đầu ra

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

Output: 1