题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26961
思路：u表示留下，~u表示离开，同理v,对于+u,-v，我们可以这样来定义：若u离开，则v必须留下，如v离开，则u必须留下,于是我们可以连边u+n->v,v+n->u,后面的同理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 20000
#define MAXM 444444 struct Edge{
int v,next;
}edge[MAXM]; int n,m,NE;
int head[MAXN]; void Insert(int u,int v)
{
edge[NE].v=v;
edge[NE].next=head[u];
head[u]=NE++;
} int cnt,bcc_count;
int low[MAXN],dfn[MAXN],color[MAXN];
bool mark[MAXN];
stack<int>S; void Tarjan(int u)
{
low[u]=dfn[u]=++cnt;
mark[u]=true;
S.push(u);
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(dfn[v]==){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(mark[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int v;
bcc_count++;
do{
v=S.top();
S.pop();
mark[v]=false;
color[v]=bcc_count;
}while(u!=v);
}
} int opp[MAXN];
bool Judge()
{
for(int i=;i<=n;i++){
if(color[i]==color[i+n])return false;
//opp[x]保存的是和编号为x的连通分量矛盾的连通分量的编号
opp[color[i]]=color[i+n];
opp[color[i+n]]=color[i];
}
return true;
} vector<vector<int> >g;
vector<int>ans;
int degree[MAXN];
int vis[MAXN]; void TopSort()
{
queue<int>que;
for(int i=;i<=bcc_count;i++){
if(degree[i]==)que.push(i);
}
while(!que.empty()){
int u=que.front();
que.pop();
if(vis[u]==){
//染色
vis[u]=;
vis[opp[u]]=-;
}
for(int i=;i<g[u].size();i++){
degree[g[u][i]]--;
if(degree[g[u][i]]==)que.push(g[u][i]);
}
}
} int main()
{
int _case,t=,a,b,u,v;
scanf("%d",&_case);
while(_case--){
scanf("%d %d",&m,&n);
NE=;
memset(head,-,sizeof(head));
while(m--){
scanf("%d%d",&a,&b);
u=abs(a),v=abs(b);
if(a>&&b>)Insert(u+n,v),Insert(v+n,u);
else if(a>&&b<)Insert(u+n,v+n),Insert(v,u);
else if(a<&&b>)Insert(u,v),Insert(v+n,u+n);
else Insert(u,v+n),Insert(v,u+n);
}
cnt=bcc_count=;
memset(mark,false,sizeof(mark));
memset(dfn,,sizeof(dfn));
memset(color,,sizeof(color));
for(int i=;i<=*n;i++)if(dfn[i]==)Tarjan(i);
printf("Case %d: ",t++);
if(!Judge()){
puts("No");
continue;
}
puts("Yes");
//反向建图
memset(degree,,sizeof(degree));
g.clear();
g.resize(*n+);
for(int u=;u<=*n;u++){
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v;
if(color[u]!=color[v]){
g[color[v]].push_back(color[u]);
degree[color[u]]++;
}
}
}
memset(vis,,sizeof(vis));
TopSort();
ans.clear();
for(int i=;i<=n;i++){
if(vis[color[i]]==)ans.push_back(i);
}
printf("%d",(int)ans.size());
sort(ans.begin(),ans.end());
for(int i=;i<(int)ans.size();i++){
printf(" %d",ans[i]);
}
puts("");
}
return ;
}