2−satは最小辞書順に実行可能解を出力する(hdu 1814)

Peaceful Commission
Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2030    Accepted Submission(s): 589
 
Problem Description
The Public Peace Commission should be legislated in Parliament of The Democratic Republic of Byteland according to The Very Important Law. Unfortunately one of the obstacles is the fact that some deputies do not get on with some others.
The Commission has to fulfill the following conditions:
1.Each party has exactly one representative in the Commission,
2.If two deputies do not like each other, they cannot both belong to the Commission.
Each party has exactly two deputies in the Parliament. All of them are numbered from 1 to 2n. Deputies with numbers 2i-1 and 2i belong to the i-th party .
Task
Write a program, which:
1.reads from the text file SPO.IN the number of parties and the pairs of deputies that are not on friendly terms,
2.decides whether it is possible to establish the Commission, and if so, proposes the list of members,
3.writes the result in the text file SPO.OUT.
 
Input
In the first line of the text file SPO.IN there are two non-negative integers n and m. They denote respectively: the number of parties, 1 <= n <= 8000, and the number of pairs of deputies, who do not like each other, 0 <= m <=2 0000. In each of the following m lines there is written one pair of integers a and b, 1 <= a < b <= 2n, separated by a single space. It means that the deputies a and b do not like each other.
There are multiple test cases. Process to end of file.
 
Output
The text file SPO.OUT should contain one word NIE (means NO in Polish), if the setting up of the Commission is impossible. In case when setting up of the Commission is possible the file SPO.OUT should contain n integers from the interval from 1 to 2n, written in the ascending order, indicating numbers of deputies who can form the Commission. Each of these numbers should be written in a separate line. If the Commission can be formed in various ways, your program may write mininum number sequence.
 
 
Sample Input
3 2 1 3 2 4
 
 
Sample Output
1 4 5
 
題意:n組の夫婦がいて、それぞれの夫婦番号は2*i-1と2*iで、それからm対の矛盾関係を与えて、各夫婦の中から1人を選んでnの集合を形成してこのn人の2人の間に矛盾がないことを保証して、もし解があれば1組の辞書の順序の最小の実行可能な解を出力しますか?
分析:まず矛盾関係に基づいて図を構築し(多くは言わない)、それからdfs暴力列挙、距離のやり方:
まず2 n個の点を無色としてマークし、最初の点から列挙し、現在の点iについて色を染めた場合は続行し、そうでなければdfsで点を変更し、検索した点について無色であれば先に赤(選択変更点を示す)、対応するi^1を青(捨てた点を示す)、検索した点が赤であれば実行可能、検索点が青であれば、i点が成功しないことを示し、さっき検索した点を無色に復元し、その対立点i^1に対してdfsを行い、実行可能であれば列挙を継続し、実行可能でなければ実行可能解は存在せず、最後に暴力的に現れる赤の点が辞書順の最も小さい実行可能解である.

#include"stdio.h"

#include"string.h"

#include"stdlib.h"

#include"queue"

#include"algorithm"

#include"string.h"

#include"string"

#include"map"

#define inf 0x3f3f3f3f

#define M 16009

using namespace std;

struct node

{

    int u,v,next;

}edge[M*20];

int t,head[M],s[M],color[M],cnt;

void init()

{

    t=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v)

{

    edge[t].v=v;

    edge[t].next=head[u];

    head[u]=t++;

}

int dfs(int u)

{

    if(color[u]==1)

        return 1;

    if(color[u]==-1)

        return 0;

    s[cnt++]=u;

    color[u]=1;

    color[u^1]=-1;

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        int v=edge[i].v;

        if(!dfs(v))

            return 0;

    }

    return 1;

}

int psq(int n)

{

    memset(color,0,sizeof(color));

    for(int i=0;i<2*n;i++)

    {

        if(color[i])continue;

        cnt=0;

        if(!dfs(i))

        {

            for(int j=0;j<cnt;j++)

                color[s[j]]=color[s[j]^1]=0;

            if(!dfs(i^1))

                return 0;

        }

    }

    return 1;

}

int main()

{

    int n,m,i;

    while(scanf("%d%d",&n,&m)!=-1)

    {

        init();

        for(i=1;i<=m;i++)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            a--;

            b--;

            add(a,b^1);

            add(b,a^1);

        }

        if(psq(n))

        {

            for(i=0;i<2*n;i++)

                if(color[i]==1)

                printf("%d
",i+1);

        }

        else

            printf("NIE
");

    }

}

#include"stdio.h"

#include"algorithm"

#include"string.h"

#include"iostream"

#include"queue"

#include"map"

#include"stack"

#include"cmath"

#include"vector"

#include"string"

#define M 20009

#define N 20003

#define eps 1e-7

#define mod 123456

#define inf 100000000

using namespace std;

struct node

{

    int v,r;

    node(){}

    node(int v,int r)

    {

        this->v=v;

        this->r=r;

    }

    bool operator<(const node &a)const

    {

        return r>a.r;

    }

};

struct st

{

    int u,v,next;

}edge[M*10];

int t,indx,num;

int head[M],low[M],dfn[M],in[M],belong[M],fp[M],top[M],use[M],color[M],mark[M],cnt;

stack<int>q;

void init()

{

    t=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v)

{

    edge[t].u=u;

    edge[t].v=v;

    edge[t].next=head[u];

    head[u]=t++;

}

void tarjan(int u)

{

    dfn[u]=low[u]=++indx;

    q.push(u);

    use[u]=1;

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].v;

        if(!dfn[v])

        {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(use[v])

        {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u])

    {

        ++num;

        int v;

        top[num]=inf;

        do

        {

            v=q.top();

            q.pop();

            belong[v]=num;

            top[num]=min(top[num],v);

            use[v]=0;

        }while(v!=u);

    }

}

int solve(int n)

{

    num=indx=0;

    memset(dfn,0,sizeof(dfn));

    memset(use,0,sizeof(use));

    for(int i=1;i<=n*2;i++)

        if(!dfn[i])

        tarjan(i);

    for(int i=1;i<=n;i++)

    {

        if(belong[i*2-1]==belong[i*2])

            return 0;

    }

    return 1;

}

int op(int u)

{

    if(u&1)

        return u+1;

    return u-1;

}

int dfs(int u)

{

    mark[++cnt]=u;

    color[u]=1;

    color[op(u)]=-1;

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].v;

        if(color[v]==-1)

            return 1;

        if(color[v]==0)

        {

            if(dfs(v))

            return 1;

        }

    }

    return 0;

}

int main()

{

    int n,m,a,b;

    while(scanf("%d%d",&n,&m)!=-1)

    {

        init();

        for(int i=1;i<=m;i++)

        {

            scanf("%d%d",&a,&b);

            if((a&1)&&(b&1))

            {

                add(a,b+1);

                add(b,a+1);

            }

            else if((a&1)&&!(b&1))

            {

                add(a,b-1);

                add(b,a+1);

            }

            else if(!(a&1)&&(b&1))

            {

                add(a,b+1);

                add(b,a-1);

            }

            else

            {

                add(a,b-1);

                add(b,a-1);

            }

        }

        int msg=solve(n);

        if(!msg)

        {

            printf("NIE
");

            continue;

        }

        memset(color,0,sizeof(color));

        for(int i=1;i<=n*2;i++)

        {

            if(!color[i])

            {

                cnt=0;

                int tt=dfs(i);

                if(tt)

                {

                    for(int j=1;j<=cnt;j++)

                        color[mark[j]]=color[op(mark[j])]=0;

                }

            }

        }

        for(int i=1;i<=2*n;i++)

        {

            if(color[i]==1)

                printf("%d
",i);

        }

    }

    return 0;

}