[POI2001]和平委员会

题目描述

根据宪法，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选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。如果委员会能以多种方法形成，程序可以只写他们的某一个。

样例输入

样例输出

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 ;

 }

巴特西