题目描述
根据宪法，Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。
此委员会必须满足下列条件：
- 每个党派都在委员会中恰有1个代表，
- 如果2个代表彼此厌恶，则他们不能都属于委员会。
每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第I个党派。
任务
写一程序：
- 从文本文件读入党派的数量和关系不友好的代表对，
- 计算决定建立和平委员会是否可能，若行，则列出委员会的成员表，
- 结果写入文本文件。
输入格式
在文本文件的第一个行有2非负整数n和m。 他们各自表示：党派的数量n，1 < =n < =8000和不友好的代表对m，0 <=m <=20000。 在下面m行的每行为一对整数a,b，1<=a
输出格式
如果委员会不能创立，文本文件中应该包括单词NIE。若能够成立，文本文件SPO.OUT中应该包括n个从区间1到2n选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。如果委员会能以多种方法形成，程序可以只写他们的某一个。
样例输入
3 2
1 3
2 4
样例输出
1
4
5 2-Sat裸题。。。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 100010
using namespace std;
struct point{
int next,to;
}e[M<<];
int n,m,num,tot,cnt,top;
int head[M],dfn[M],st[M],low[M],co[M];
bool vis[M];
void add(int from,int to)
{
e[++num].next=head[from];
e[num].to=to;
head[from]=num;
}
void tarjan(int x)
{
low[x]=dfn[x]=++cnt;
st[++top]=x;
vis[x]=true;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(!dfn[to])
{
tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to]) low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x])
{
tot++;
while(st[top+]!=x)
{
co[st[top]]=tot;
vis[st[top]]=false;
top--;
}
}
}
bool two_sat()
{
for(int i=;i<=*n;i++)
if(!dfn[i])
tarjan(i);
for(int i=;i<=n;i++)
if(co[i*-]==co[i*])
return false;
return true;
}
int main()
{
//freopen("spo.in","r",stdin);
//freopen("spo.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int A,B,AA,BB;
scanf("%d%d",&A,&B);
if(A%==) AA=A-;
else AA=A+;
if(B%==) BB=B-;
else BB=B+;
add(AA,B); add(BB,A);
}
if(two_sat())
{
for(int i=;i<=n;i++)
printf("%d\n",co[i*-]>co[i*]?i*-:i*);
}
else printf("NIE");
return ;
}