C++ Program to check if two stacks of letters can be emptied or not

Suppose, there are 2n number of letters and each of them has an integer number between 1 to n written on them. There are exactly two letters that have the same number written on them. These letters are arranged into m stacks and stack i has letters stack[i] on it. Our task is to empty all the stacks in the following manner

• We have to choose any two stacks and remove the top letter from both of them.

• The letters that we have removed must have the same number on both of them.

If we can empty the m stacks in this manner, we print true or otherwise we return false.

So, if the input is like n = 3, m = 2, stacks = {{2, 1, 3}, {2, 1, 3}}, then the output will be true.

There are two stacks and each of the stacks has letters that have the numbers 2, 1, 3 written on them respectively. So, we can remove from the two stacks and empty them in the given manner.

To solve this, we will follow these steps −

Define one 2D array dp Define an array tvec for initialize i := 0, when i < m, update (increase i by 1), do:    k := size of stacks[i]    for initialize j := 0, when j < k, update (increase j by 1), do:       if j < 0, then:          insert p at the end of dp[stacks[i, j]]          (increase tvec[p] by 1)       p := stacks[i, j] Define an array tp for initialize i := 1, when i <= n, update (increase i by 1), do:    Define one queue q    insert i into q    while (q is not empty), do:     if not tp[first element of q] and tvec[first element of q] is same as 0, then:          for each element next in dp[first element of q], do:              (decrease tvec[next] by 1)             insert next into q tp[first element of q] := true delete first element from q for initialize i := 1, when i <= n, update (increase i by 1), do: if tvec[i] is not equal to 0, then: return false return true

Example

Let us see the following implementation to get better understanding −

#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