2-SAT。
假设a,a’一组，b,b’一组，那么如果a和b矛盾，选a就肯定要选b’，于是连一条边a->b’，同理有连边b->a’
然后暴力找答案，dfs(i)的返回值表示选i是否引起矛盾
因为这些对应关系是组与组之间的，所以假设当前选i不矛盾，那么接下来的其他没决策过的点的决策与i无关，即i决策不会改变（否则考虑i的时候就会被考虑）
数组大小很迷 开大点总是好的
#include<cstdio> #include<cstring> using namespace std; int c[80005<<1],cnt=0, last[80005<<1], match[80005], mc=0; struct edge{int next,to;}e[200010<<1]; void add(int a, int b){e[++cnt]=(edge){last[a],b};last[a]=cnt;} int opp(int x){return x&1?x+1:x-1;} int dfs(int u) { if(c[u]!=0)return c[u]==1?1:0; c[u]=1; c[opp(u)]=-1; match[++mc]=u; for(int i = last[u]; i; i=e[i].next) { int v=e[i].to; if(!dfs(v))return 0; } return 1; } int main() { int n, m; bool flag; while(~scanf("%d%d",&n,&m)) { cnt=0;flag=1; memset(last,0,sizeof(last)); memset(c,0,sizeof(c)); for(int i = 1; i <= m; i++) { int a, b; scanf("%d%d",&a,&b); add(a,opp(b)); add(b,opp(a)); } for(int i = 1; i <=(n<<1); i++) { if(c[i]!=0)continue; mc=0; if(!dfs(i)) { for(int j = 1; j <= mc; j++) c[match[j]]=c[opp(match[j])]=0; if(!dfs(opp(i))) { flag=0; break; } } } if(!flag) { printf("NIE\n"); continue; } else for(int i = 1; i <= (n<<1); i++) if(c[i]==1) printf("%d\n",i); } }