POI 2001
根据宪法，Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。
此委员会必须满足下列条件：
每个党派都在委员会中恰有1个代表，
如果2个代表彼此厌恶，则他们不能都属于委员会。
每个党在议会中有 2 个代表。代表从1编号到2n。编号为2i-1和2i的代表属于第i个党派。
任务：写一程序读入党派的数量和关系不友好的代表对，计算决定建立和平委员会是否可能，若行，则列出委员会的成员表。
输入格式
第一行有两个非负整数n和m。他们各自表示：党派的数量n和不友好的代表对 m。 接下来 m 行，每行为一对整数 a，b表示代表a,b互相厌恶。
输出格式
如果不能创立委员会，则输出信息NIE。若能够成立，则输出包括 n 个从区间 1 到 2n选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。
如果委员会能以多种方法形成，程序可以只输出它们的某一个。
样例
样例输入
3 2
1 3
2 4
样例输出
1
4
5
数据范围与提示
1<=n<=8000,0<=m<=20000,1<=a<b<=2n
————————————————————————————————
2-SAT问题。用对称性解！
————————————————————————————————
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=8010; 4 const int maxm=2e4+10; 5 struct edge 6 { 7 int u,v,nxt; 8 }e[maxm<<1]; 9 int head[maxn<<1],js; 10 void addage(int u,int v) 11 { 12 e[++js].u=u;e[js].v=v; 13 e[js].nxt=head[u];head[u]=js; 14 } 15 int n,m; 16 int dfn[maxn<<1],low[maxn<<1],cnt,lt[maxn<<1],lts,st[maxn<<1],top; 17 void tarjan(int u) 18 { 19 dfn[u]=low[u]=++cnt; 20 st[++top]=u; 21 for(int i=head[u];i;i=e[i].nxt) 22 { 23 int v=e[i].v; 24 if(!dfn[v]) 25 { 26 tarjan(v); 27 low[u]=min(low[u],low[v]); 28 } 29 else if(!lt[v]) low[u]=min(low[u],dfn[v]); 30 } 31 if(low[u]==dfn[u]) 32 { 33 lt[u]=++lts; 34 while(st[top]!=u)lt[st[top--]]=lts; 35 --top; 36 } 37 } 38 int main() 39 { 40 scanf("%d%d",&n,&m); 41 for(int a,b,i=0;i<m;++i) 42 { 43 scanf("%d%d",&a,&b); 44 addage(a,b&1?b+1:b-1); 45 addage(b,a&1?a+1:a-1); 46 } 47 for(int i=1;i<=(n<<1);++i) 48 if(!dfn[i])tarjan(i); 49 for(int i=1;i<=n;++i) 50 { 51 if(lt[i<<1]==lt[(i<<1)-1]) 52 { 53 printf("NIE"); 54 return 0; 55 } 56 } 57 for(int i=1;i<=n;++i) 58 { 59 if(lt[i<<1]<lt[(i<<1)-1]) 60 printf("%d\n",i<<1); 61 else printf("%d\n",(i<<1)-1); 62 } 63 return 0; 64 }
原文：https://www.cnblogs.com/gryzy/p/10892920.html
