思路：刚看这道题感觉什么都不清楚，人物之间的关系一点也看不出来，都不知道怎么写，连并查集都没看出来，但是你可以仔细分析一下，当输入字符串为“yes”的时候，我们设输入的值为x和y，当x为天使是则由题可知y也为天使；当x为魔鬼的时候，则y也为魔鬼，所以输入“yes”的时候就相当于说他们是同类。
当输入字符串为“no”的时候，如果x为天使，则y为魔鬼；x为魔鬼的时候，y就是天使，所以当输入字符串为“no”的时候他们为异类。。这不就是种类并查集的
0 （同类） 1（异类）并查集嘛！
再接着想，通过并查集我们可以把它们分成两类，一种是和他们的根节点同类，一种不是同类。。这一点要注意了，所有的他们并不是一定是一个父节点，假如
（1 2）（3 4） 那他们就不在一棵树上。。
用完并查集我们就要用一个数组来记录他们根节点的数目，而且还要记录每一个根节点与其同类和异类的两种情况的数目，然后我们只要用这些数可以组合出来
天使或魔鬼的数目就可以了，但是要保证只有一种方法可以，如果有好几种方法，那就无法确定。。还要注意的是当去组成天使或魔鬼的数目的时候，一个根节点只能选根节点的同类或异类来往上加，不能都选。。。
上一点是不是有点像01背包，用一些数来组成一个数，看有几种方法
最后就是输出路径（路径方法我之前写过，你也可以在网上搜一下）
接着就上代码吧！
//https://www.cnblogs.com/geloutingyu/p/6142473.html 我是看这个网址才懂得，可以看一下
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int v[],w[],n,a,b,gg[],jj[][],tag[][],dp[][],cc[][];
struct shudui
{
int start,last;
char q;
}m[];
int finds(int x)
{
if(x!=v[x])
{
int y=finds(v[x]);
w[x]=(w[x]+w[v[x]])%;
v[x]=y;
return y;
}
return x;
}
void join(int x,int y,int z)
{
int fx=finds(x);
int fy=finds(y);
if(fx==fy)
{
return;
}
else
{
v[fx]=fy;
w[fx]=(-w[x]+z-+w[y])%;
}
}
int main()
{
while(~scanf("%d%d%d",&n,&a,&b))
{
memset(w,,sizeof(w));
if(n+a+b==) break;
for(int i=;i<=a+b;++i)
{
v[i]=i;
}
while(n--)
{
char q[];
int x,y;
scanf("%d%d%s",&x,&y,q);
if(x==y)
continue;
if(strcmp("no",q)==)
{
join(x,y,);
}
else join(x,y,);
}
//int w1[1005],w2[1005];
memset(gg,,sizeof(gg)); //存根节点
memset(jj,,sizeof(jj));
memset(tag,,sizeof(tag)); //来记录根节点同来和异类的数目
memset(dp,,sizeof(dp)); //背包dp，看看有几种方法
memset(cc,,sizeof(cc)); //标记，做最后输出
int cnt=;
for(int i=;i<=a+b;++i) //统计集合个数
{
if(finds(i)==i)
{
gg[i]=++cnt;
}
}
for(int i=;i<=a+b;++i)
{
tag[gg[finds(i)]][w[i]]++;
}
dp[][]=;
for(int i=;i<=cnt;++i)
{
for(int j=;j<=a;++j)//dp[i][j]表示到第i个集合，人数达到j的方法数
{
if(j-tag[i][]>= && dp[i-][j-tag[i][]])
{
dp[i][j]+=dp[i-][j-tag[i][]];
jj[i][j]=tag[i][]; //jj是记录路径的
}
if(j-tag[i][]>= && dp[i-][j-tag[i][]])
{
dp[i][j]+=dp[i-][j-tag[i][]];
jj[i][j]=tag[i][];
}
}
}
if(dp[cnt][a]!=)
{
printf("no\n");
}
else
{
for(int i=cnt,j=a;j> && i>; i--)
{
if(jj[i][j]==tag[i][])
cc[i][]=;
else cc[i][]=;
j-=jj[i][j];
}
for(int i=;i<=a+b;++i)
{
if(cc[gg[finds(i)]][w[i]]) printf("%d\n",i);
}
printf("end\n");
}
}
return ;
}