把每個政黨的兩個議員看作兩個頂點，不能相處的議員之間連接一條邊。類似於二分圖的染色，但又不是嚴格的二分圖。我們規定第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