题目大意
有n种颜色,m个圆柱体,每一种颜色都有2个小球,小球放在这m个圆柱体里面,每次只能取走圆柱体最上面的相同颜色的小球,问能不能取走所有的小球
思路
把这m个圆柱体看做m个队列,分别遍历这m个队列,当第二次遇到同一颜色的小球时,把这两个小球拿走, 看最后还有没有小球在圆柱体面,如果有,那么就不能取走
vis[i] = 1:小球之前出现过
mp[i] = a:第i个小球之前出现过的位置在第a个圆柱体最上面
空间复杂度稍稍有一点大,还是可以过
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int N = 2e5 + 10;
int n, m;
unordered_map<int, int=""> mp;
vector<queue<int>> q(N);
bool vis[N];
void dfs(int i)
{
//mp.count(q[pos].front())
int pos = mp[q[i].front()];
q[pos].pop();
q[i].pop();
while(!q[pos].empty() && vis[q[pos].front()])
{
dfs(pos);
}
if(!q[pos].empty())
{
vis[q[pos].front()] = 1;
mp[q[pos].front()] = pos;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
for (int j = 1; j <= x; j++)
{
int t;
cin >> t;
q[i].push(t);
}
}
for(int i = 1; i <= m; i++)
{
while(!q[i].empty() && vis[q[i].front()])
{
dfs(i);
}
if(!q[i].empty()) //记录栈顶元素时记得不要越界了
{
vis[q[i].front()] = 1;
mp[q[i].front()] = i;
}
}
/*
2 2
2
1 2
2
1 2
*/
int flag = 0;
for (int i = 1; i <= m; i++)
{
if (!q[i].empty())
{
flag = 1;
break;
}
}
if (flag)
puts("No");
else
puts("Yes");
}
```</queue<int></int,></queue></vector></string></algorithm></unordered_map></cstring></iostream>