题意：输入n,m,x,y;表示有n个人，输入m种对立关系，输入x个确认好人的标号，y个确认坏人的标号
思路：我们可以从确定的好人和坏人出发，有错误身份的输出NO，最后有不确定的输出NO，否则YES。
1 #include<bits/stdc++.h> 2 using namespace std; 3 map<int ,int >mp; 4 vector<int >p[1003]; 5 int sum,f; 6 void init(){ 7 mp.clear(); 8 for(int i=0;i<1003;i++) 9 p[i].clear(); 10 sum=0;f=0; 11 } 12 void dfs(int x,int y) { 13 if(f) return ; 14 for(int i=0;i<p[x].size();i++){ 15 if( mp[p[x][i]]==y ) { f=1; return ;} 16 if( mp[p[x][i]]==0 ){ 17 sum++; 18 mp[p[x][i]]=-y; 19 dfs(p[x][i],-y); 20 } 21 } 22 } 23 int main() 24 { 25 int n,m,x,y; 26 int a,b; 27 while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){ 28 init(); 29 for(int i=1;i<=m;i++) { 30 scanf("%d%d",&a,&b); 31 p[a].push_back(b);p[b].push_back(a); 32 } 33 34 for(int i=1;i<=x;i++){ 35 scanf("%d",&a); 36 if(f==1) continue; 37 if(mp[a]==-1) {f=1;continue;} 38 if(mp[a]==0) { 39 mp[a]=1; dfs(a,1);sum++; 40 } 41 } 42 for(int i=1;i<=y;i++) { 43 scanf("%d",&b); 44 if(f==1) continue; 45 if(mp[b]==1) {f=1;continue;} 46 if(mp[b]==0){ 47 mp[b]=-1;dfs(b,-1);sum++; 48 } 49 } 50 for(int i=1;i<=n;i++){ 51 if(mp[i]==0){ 52 if(p[i].size()==0){f=1;break;} 53 mp[i]=1; 54 sum++; 55 dfs(i,1); 56 } 57 } 58 if(sum==n&&f==0) printf("YES "); 59 else printf("NO "); 60 } 61 return 0; 62 }