P4355 [CERC2015]Kernel Knights
TsH_GD
·
·
题解
此题的第一篇题解（也是我的第一篇题解）
题链
分析
没人攻击的骑士一定在 \rm kernel 里，把没人攻击的加入队列，然后被他攻击的骑士一定在 \rm kernel 外。
于是 被 外面的骑士攻击 的骑士 的被攻击次数 `-1`，如果被攻击次数为 $0$ 了就加入队列。
某个导致我 `WA` 的地方：被攻击次数 `-1` 这个操作不能重复，所以要判断当前这个“外面的骑士”是不是已经处理过。
## code:
```cpp
#include<queue>
#include<cstring>
using namespace std;
const int maxn=2e5+100;
int n,a[maxn],d[maxn],k[maxn];
queue<int> q;
int main()
{
while(~scanf("%d",&n))
{
while(!q.empty()) q.pop();
memset(d,0,sizeof(d));
memset(k,0,sizeof(k));
for(int i=1; i<=2*n; i++)
{
scanf("%d",&a[i]);
d[a[i]]++;
}
for(int i=1; i<=2*n; i++)
{
if(d[i]==0)q.push(i);
}
while(!q.empty())
{
int p=q.front();
q.pop();
k[p]=1;
if( k[ a[p] ]==-1 )continue;//没有它而让我WA的地方
k[a[p]]=-1;
d[a[a[p]]]--;
if(d[a[a[p]]]==0)q.push(a[a[p]]);
}
for(int i=1; i<=2*n; i++)
{
if(i<=n&&k[i]>=0)printf("%d ",i);
else if(k[i]==1)printf("%d ",i);
}
printf("\n");
}
return 0;
}
```
qwq，一定要过啊