This post is written in Chinese. Please consider using Google Translate

把每个政党的两个议员看作两个顶点，不能相处的议员之间连接一条边。类似于二分图的染色，但又不是严格的二分图。我们规定第2i-1和2i个顶 点为姊妹顶点。对于图中的每个连通分量，尝试从首个顶点开始访问染色，规定其加入理事会，然后访问该顶点的邻接顶点的姊妹顶点。遍历中如果发现了一对姊妹 顶点都被加入了理事会，则是不合法的，染色失败。如果染色成功，继续查找下一个连通分量，否则重新尝试从首个顶点的姊妹顶点开始访问染色，如果染色成功， 继续查找下一个连通分量，否则染色失败，不可能组建理事会。

该算法巧妙的类比了二分图染色，并根据该题的特点，设计出合适的方案，时间复杂度为O(M)。

/* 
 * Problem: POI2001 spo
 * Author: Guo Jiabao
 * Time: 2009.1.28 0:58
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=16001,MAXM=36001;

struct list
{
    list *next;
    int t;
};

struct adjl
{
    list *f,*l;
};

adjl A[MAXN];
list L[MAXM];
int N,M,Lc;
bool S[MAXN],TS[MAXN];

void addedge(int a,int b)
{
    if (A[a].f)
        A[a].l=A[a].l->next=&L[++Lc];
    else
        A[a].l=A[a].f=&L[++Lc];
    L[Lc].t=b;
}

void init()
{
    int i,a,b;
    freopen("spo.in","r",stdin);
    freopen("spo.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
}

inline int getop(int k)
{
    if (k%2) return k+1;
    else return k-1;
}

bool deal(int a)
{
    int b,bo,ao;
    S[a]=true;
    ao=getop(a);
    if (S[ao])
        return false;
    for (list *k=A[a].f;k;k=k->next)
    {
        b=k->t;
        bo=getop(b);
        if (!S[bo] && !deal(bo))
            return false;
    }
    return true;
}

void print(bool k)
{
    if (k)
    {
        for (int i=1;i<=N*2;i++)
            if (S[i])
                printf("%dn",i);
    }
    else
        printf("NIEn");
}

void cpy(bool *A,bool *B)
{
    for (int i=1;i<=N*2;i++)
        B[i]=A[i];
}

bool solve(int k)
{
    if (!deal(k))
    {
        cpy(TS,S);
        if (!deal(k+1))
            return false;
    }
    cpy(S,TS);
    return true;
}

void compute()
{
    for (int i=1;i<=N*2;i+=2)
    {
        if (S[i]==0)
        {
            if (!solve(i))
            {
                print(false);
                return;
            }
        }
    }
    print(true);
}

int main()
{
    init();
    compute();
    return 0;
}

<h2><span class="mw-headline">和平委员会 </span></h2>

根据宪法，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 <b<=2n，中间用单个空格隔开。 它们表示代表a,b互相厌恶。

  输出

  如果委员会不能创立，文本文件中应该包括单词NIE。若能够成立，文本文件SPO.OUT中应该包括n个从区间1到2n选出的整数，按升序写出，每行一个，这些数字为委员会中代表的编号。如果委员会能以多种方法形成，程序可以只写他们的某一个。

  样品输入

  3 2
    1 3
    2 4

  样品输出

  1
    4
    5