题目链接：

思路：u表示留下，~u表示离开，同理v,对于+u,-v，我们可以这样来定义：若u离开，则v必须留下，如v离开，则u必须留下,于是我们可以连边u+n->v,v+n->u,后面的同理。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 using namespace std; 9 #define MAXN 20000 10 #define MAXM 444444 11 12 struct Edge{ 13 int v,next; 14 }edge[MAXM]; 15 16 int n,m,NE; 17 int head[MAXN]; 18 19 void Insert(int u,int v) 20 { 21 edge[NE].v=v; 22 edge[NE].next=head[u]; 23 head[u]=NE++; 24 } 25 26 int cnt,bcc_count; 27 int low[MAXN],dfn[MAXN],color[MAXN]; 28 bool mark[MAXN]; 29 stack
             
              S; 30 31 void Tarjan(int u) 32 { 33 low[u]=dfn[u]=++cnt; 34 mark[u]=true; 35 S.push(u); 36 for(int i=head[u];i!=-1;i=edge[i].next){ 37 int v=edge[i].v; 38 if(dfn[v]==0){ 39 Tarjan(v); 40 low[u]=min(low[u],low[v]); 41 }else if(mark[v]){ 42 low[u]=min(low[u],dfn[v]); 43 } 44 } 45 if(low[u]==dfn[u]){ 46 int v; 47 bcc_count++; 48 do{ 49 v=S.top(); 50 S.pop(); 51 mark[v]=false; 52 color[v]=bcc_count; 53 }while(u!=v); 54 } 55 } 56 57 int opp[MAXN]; 58 bool Judge() 59 { 60 for(int i=1;i<=n;i++){ 61 if(color[i]==color[i+n])return false; 62 //opp[x]保存的是和编号为x的连通分量矛盾的连通分量的编号 63 opp[color[i]]=color[i+n]; 64 opp[color[i+n]]=color[i]; 65 } 66 return true; 67 } 68 69 vector
              
               
                 >g; 70 vector
                
                 ans; 71 int degree[MAXN]; 72 int vis[MAXN]; 73 74 void TopSort() 75 { 76 queue
                 
                  que; 77 for(int i=1;i<=bcc_count;i++){ 78 if(degree[i]==0)que.push(i); 79 } 80 while(!que.empty()){ 81 int u=que.front(); 82 que.pop(); 83 if(vis[u]==0){ 84 //染色 85 vis[u]=1; 86 vis[opp[u]]=-1; 87 } 88 for(int i=0;i
                  
                   0&&b>0)Insert(u+n,v),Insert(v+n,u);108 else if(a>0&&b<0)Insert(u+n,v+n),Insert(v,u);109 else if(a<0&&b>0)Insert(u,v),Insert(v+n,u+n);110 else Insert(u,v+n),Insert(v,u+n);111 }112 cnt=bcc_count=0;113 memset(mark,false,sizeof(mark));114 memset(dfn,0,sizeof(dfn));115 memset(color,0,sizeof(color));116 for(int i=1;i<=2*n;i++)if(dfn[i]==0)Tarjan(i);117 printf("Case %d: ",t++);118 if(!Judge()){119 puts("No");120 continue;121 }122 puts("Yes");123 //反向建图124 memset(degree,0,sizeof(degree));125 g.clear();126 g.resize(2*n+2);127 for(int u=1;u<=2*n;u++){128 for(int i=head[u];i!=-1;i=edge[i].next){129 int v=edge[i].v;130 if(color[u]!=color[v]){131 g[color[v]].push_back(color[u]);132 degree[color[u]]++;133 }134 }135 }136 memset(vis,0,sizeof(vis));137 TopSort();138 ans.clear();139 for(int i=1;i<=n;i++){140 if(vis[color[i]]==1)ans.push_back(i);141 }142 printf("%d",(int)ans.size());143 sort(ans.begin(),ans.end());144 for(int i=0;i<(int)ans.size();i++){145 printf(" %d",ans[i]);146 }147 puts("");148 }149 return 0;150 }