D - Pair of Balls
题意
有\(N\)种颜色的球，每种颜色有\(2\)个，共\(2N\)个球，现将它们放置在\(M\)个栈中，每个栈有\(k_i\)个球，每次从两个不同的栈顶取出相同颜色的球，问是否能够取完，可以则输出\(Yes\)，否则输出\(No\)。
思路
我们可以将每个栈看成一个单链表，从栈顶连向栈底，因此当我们可以选择某种颜色出栈的时候，说明此时没有边连向该种颜色，也就可以认为是入度为\(0\)的时候可以出栈，那么问题就可以转化成为拓扑排序能否执行\(n\)次。因此我们只需要建图再跑一遍拓扑排序即可。
参考代码
点此展开
//Author:Daneii
#include <bits/stdc++.h>
using namespace std;
//快读
template <typename T>inline void read(T& t)
{
int f=0;
t=0;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=1;
ch=getchar();
}
while(isdigit(ch))
{
t=t*10+ch-48;
ch=getchar();
}
t=f?-t:t;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
const int N=2e5+10;
int n,m;
vector<int> g[N];
int deg[N];
bool topsort()
{
queue<int> q;
for(int i=1;i<=n;i++)
if(!deg[i])
q.push(i);
int cnt=0;
while(q.size())
{
auto tmp=q.front();
q.pop();
cnt++;
for(auto x:g[tmp])
{
if(--deg[x]==0)
{
q.push(x);
}
}
}
return cnt==n;
}
int main()
{
read(n,m);
for(int i=1;i<=m;i++)
{
int k;
read(k);
int u=0,v;
for(int j=1;j<=k;j++)
{
if(j==1) read(u);
else
{
read(v);
g[v].push_back(u);
deg[u]++;
u=v;
}
}
}
if(topsort()) puts("Yes");
else puts("No");
return 0;
}