1519：和平委员会

【题目描述】

原题来自：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 模板题

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3e6 + 109;
int e[N],w[N],ne[N],h[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],in_stk[N],top;
int id[N],scc_cnt;
int n, m;
int a[N], b[N];

void add(int a,int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = 1;
    for(int i = h[u]; ~i ; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j])
        {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if(dfn[u] == low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            in_stk[y] = 0;
            id[y] = scc_cnt;
        } while (y != u);
    }
}
#define calc(a) a&1 ? a + 1: a - 1
int main()
{
    scanf("%d %d",&n,&m);
    memset(h, -1, sizeof(h));
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d %d",&x,&y);
        add(x, calc(y));
        add(y, calc(x));
    }

    for(int i = 1; i <= n * 2; i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 1; i <= n * 2; i += 2)
    {
        if(id[i] == id[i + 1])
        {
            // printf("\n\n");
            // printf("%d %d",id[i],id[i + 1]);
            printf("NIE");
            return 0;
        }
    }
    for(int i = 1; i <= n * 2; i+=2)
    {
        if(id[i] < id[i + 1])
        {
            printf("%d\n", i);
        }
        else printf("%d\n",i + 1);
    }
    return 0;
}

1519：和平委员会

推荐阅读