题意

有$n$行输入形如$x$, $y$, $str$，$str$为yes表示$x$说$y$是天使，$str$为no表示$x$说$y$不是天使($x$, $y$为天使，恶魔的编号，$1<=x,y<=p+q$)；天使只说真话，恶魔只说假话；如果不能确定所有天使的编号，输出no，若能确定，输出所有天使的编号，并且以end结尾；注意：可能会有连续两行一样的输入；

解题思路

注意到若回答yes，则$x$ $y$必同种类，否则$x$ $y$必异种类，所以通过种类并查集分类。

维护完并查集之后并不能确定哪些是好人哪些是坏人，只能确定相对关系，想要得到准确唯一的确定答案，必须要严格证明有且只有一种情况满足$p$个好人，$q$个坏人。

首先先统计出每个根节点下$r[x] = 1$和$r[x] = 0$的数目，然后做01背包，把集合堆$tot$的数目当做商品种类，好人个数$p$当做背包容量，计算从$tot$个堆从选出$p$个好人的方法有多少种。如果只有一种方法那么必定可以确定好人数目。

最后就是路径回溯，记录一下好人的序号按照升序打印就完毕了，那就利用一下set集合，或者数组记录排序都行。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1505 ;    
int n,p1,p2,cnt;
int f[N],dp[N][N],v[N],g[N],set[N][5];

int find(int x){
    if(f[x]==x) return x;
    int tmp = f[x];
    f[x]=find(f[x]);
    v[x]=(v[x]+v[tmp])%2;
    return f[x];
}

int main(){
    while(~scanf("%d%d%d",&n,&p1,&p2)){
        if(!n && !p1 &&!p2) break;
        cnt = 0;memset(set,0,sizeof(set));memset(dp,0,sizeof(dp)); 
        memset(f,-1,sizeof(f));
        for(int i=1;i<=p1+p2;i++) f[i]=i,v[i]=0;
        char s[10];int x,y;
        for(int k=1;k<=n;k++){
            scanf("%d%d %s",&x,&y,s);
            int fx=find(x),fy=find(y);
            if(fx==fy) continue ;
            f[fx]=fy;
            if(s[0]=='y') v[fx]=(v[x]+v[y])%2;
            else v[fx]=(v[x]+v[y]+1)%2;
        }
        for(int i=1;i<=p1+p2;i++){
            if(find(i)==i) g[i]=++cnt;
        }
        for(int i=1;i<=p1+p2;i++) set[g[find(i)]][v[i]]++;//set数组记录第几组两类的个数 
        dp[0][0]=1;//dp[i,j]前i个集合，和为j的情况数量 
        for(int i=1;i<=cnt;i++){
            for(int j=0;j<=p1;j++){  //注意p1等于0的情况 
                if(j>=set[i][0]) dp[i][j]+=dp[i-1][j-set[i][0]]; 
                if(j>=set[i][1]) dp[i][j]+=dp[i-1][j-set[i][1]];
            }
        } 
        int tmp = p1;
        int choose[N];
        memset(choose,-1,sizeof(choose));
        if(dp[cnt][p1]==1){
            for(int i=cnt;i>=1;i--){
                if(dp[i-1][tmp-set[i][0]]==dp[i][tmp]){
                    choose[i]=0;
                    tmp-=set[i][0];
                }else if(dp[i-1][tmp-set[i][1]]==dp[i][tmp]){
                    choose[i]=1;
                    tmp-=set[i][1];
                }
            }
            for(int i=1;i<=p1+p2;i++){
                if(choose[g[find(i)]]==v[i]) printf("%d\n",i);
            }
            puts("end");
        }else puts("no");
    }
    return 0;
}