题意
有两个队的骑士1到n和n 1到2n，每个骑士只能互相攻击对手队的一个骑士。kernel的意思是在这个kernel里的骑士不会互相攻击，在kernel外的骑士被kernel里的骑士攻击。
现在告诉你所有骑士攻击的骑士，求一个kernel。
分析
没人攻击的骑士一定在kernel里，把没人攻击的加入队列，然后被他攻击的骑士一定在kernel外。
kernel外的骑士的攻击无效，因为如果一个骑士如果只被外面的骑士攻击，他就是kernel里的。
于是 被 外面的骑士攻击 的骑士 的被攻击次数 -1，如果被攻击次数为0了就加入队列。
某个导致我WA的地方：被攻击次数 -1 这个操作不能重复，所以要判断当前这个“外面的骑士”是不是已经处理过。
反例： 4 5 5 8 7 3 3 4 4 正确答案：1 2 6 7 8 重复操作的错误答案：1 2 3 6 7 8
处理完后，剩下的就是一个边数为偶数的环，只要输出它的一边就好了。
这题也可以DFS。
代码
代码语言：javascript复制#include<cstdio>
#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;
}
