题意：有两队骑士各n人，每位骑士会挑战对方队伍的某一个位骑士. (可能相同)
要求找以一个区间s： 集合S中的骑士不会互相挑战. 每个集合外的骑士必定会被集合S内的某个骑士挑战.题解：讲真被题目绕懵比了，一直不知道题目在要求找啥。
骑士可以分为三类：必定在s中，必定不再s中，不确定的。 如果一个骑士的被挑战人数为0的话，那么他一定在s中。（否则就违背了2） 如果一个骑士挑战了确定在s内的骑士，那么他一定在圈外。 若某个骑士i被多个人挑战，那么要先对这些挑战者逐一进行上述判断，若某个挑战者被确定在S外，那么说明能使骑士i满足条件2的挑战者少了一个(等同于少了一个挑战者). 若所有挑战者都在S外，那么i一定在S内。最后会有一种情况，就是该骑士跟挑战者都不能确定在圈外还是圈内，如样例的1、5，这时候让他们任意一人在圈内就可以了。
#include#include #include #include #include #include using namespace std;const int maxn = 200050;int ans[maxn],f[maxn],head[maxn],vis[maxn];void dfs(int x){ vis[x] = 1; if(vis[head[x]]==1) return; if(f[x]==1) { f[head[x]] = -1; dfs(head[x]); return; } ans[head[x]] --; if(!ans[head[x]]) { f[head[x]] = 1; dfs(head[x]); return; }}int main(){ int n,i,x,ff; cin>>n; memset(ans,0,sizeof(ans)); memset(f,0,sizeof(ans)); memset(head,0,sizeof(ans)); memset(vis,0,sizeof(ans)); for(i=1;i<=2*n;i++) { scanf("%d",&x); ans[x] ++; head[i] = x; } for(i=1;i<=2*n;i++) if(!ans[i]&&!vis[i]) { f[i] = 1; dfs(i); } ff = 0; for(i=1;i<=2*n;i++) { if(f[i]==-1) continue; if(f[i]==1) { if(!ff) { printf("%d",i); ff = 1; } else printf(" %d",i); continue; } if(i<=n) { if(!ff) { printf("%d",i); ff = 1; } else printf(" %d",i); } } printf("\n"); return 0;}