hdu 1814 2-sat 输出字典最小的和任意序列的模板题

/*

思路：http://blog.csdn.net/string_yi/article/details/12686873

hdu  1814  输出字典序最小的2-sat

*/

#include<stdio.h>

#include<string.h>

#include<math.h>

#define N 16100

#define NN  210000

struct node {

  int v,w,next;

}bian[NN*2];

int head[N],cnt,yong,color[N],ans[N];

void init() {

yong=0;

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

yong=0;

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

}

void addedge(int u,int v) {

bian[yong].v=v;

bian[yong].next=head[u];

head[u]=yong++;

}

int  dfs(int v)

{

    if(color[v]==2)

     return 0;

    if(color[v]==1)

     return 1;

     ans[cnt++]=v;

    color[v]=1;

    color[v^1]=2;

    for(int i=head[v];i!=-1;i=bian[i].next)

     if(!dfs(bian[i].v))

      return 0;

    return 1;

}

void slove(int n) {

int i,j;

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

    if(color[i])continue;

     cnt=0;

    if(!dfs(i)) {

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

        color[ans[j]]=0;

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

       }

       if(!dfs(i^1)) {

        printf("NIE\n");

        return ;

       }

    }

}

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

    if(color[i]==1)

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

    else

        printf("%d\n",i+2);

}

}

int main() {

   int n,aa,bb,m;

   while(scanf("%d%d",&n,&m)!=EOF) {

        init();

    while(m--) {

        scanf("%d%d",&aa,&bb);

        aa--;bb--;

        addedge(aa,bb^1);

        addedge(bb,aa^1);

    }

    slove(n);

   }

return 0;}

输出任意次序<pre name="code" class="cpp">/*

hit 1917输出任意次序的2-sat

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <vector>

using namespace std;

const int maxn=16005;

const int maxm=200005;

int head[maxn],next[maxm],to[maxm];

int dfn[maxn],low[maxn],stk[maxn],scc[maxn],ind[maxn],vis[maxn];

int color[maxn],f[maxn];

int tot,top,cnt,id;

vector<int> dag[maxn];

void addEdage(int u,int v)

{

    next[tot]=head[u],to[tot]=v,head[u]=tot++;

}

void init()

{

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

    memset(vis,0,sizeof(vis));

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

    memset(ind,0,sizeof(ind));

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

    tot=top=cnt=id=0;

}

void tarjan(int v)

{

    dfn[v]=low[v]=++cnt;

    vis[v]=1;

    stk[++top]=v;

    for(int i=head[v];i!=-1;i=next[i])

    {

        int u=to[i];

        if(!dfn[u])

        {

            tarjan(u);

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

        }

        else if(vis[u])

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

    }

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

    {

        id++;

        while(true)

        {

            int u=stk[top--];

            vis[u]=0;

            scc[u]=id;

            if(u==v)break;

        }

    }

}

void buildDag(int n)

{

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

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

        {

            int v=to[i];

            if(scc[v]!=scc[u])

            {

                dag[scc[v]].push_back(scc[u]);

                ind[scc[u]]++;

            }

        }

}

void topsort()

{

    queue<int> q;

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

     if(!ind[i])q.push(i);

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         if(!color[u])

          color[u]=1,color[f[u]]=2;

          for(int i=0;i<(int)dag[u].size();i++)

          {

              int v=dag[u][i];

              ind[v]--;

              if(!ind[v])q.push(v);

          }

     }

}

void solve(int n)

{

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

     if(!dfn[i])tarjan(i);

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

     if(scc[i]==scc[i+1])

     {

         printf("NIE\n");

         return;

     }

    else f[scc[i]]=scc[i+1],f[scc[i+1]]=scc[i];

    for(int i=0;i<=id;i++)

    dag[i].clear();

    buildDag(n);

    topsort();

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

    {

        if(color[scc[i]]==1)

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

        else

        printf("%d\n",i+2);

    }

}

int main()

{

//     freopen("in.txt","r",stdin);

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        init();

        for(int i=0,a,b;i<m;i++)

        {

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

            a--,b--;

            addEdage(a,b^1);

            addEdage(b,a^1);

        }

        solve(n);

    }

    return 0;

}

巴特西

hdu 1814 2-sat 输出字典最小的和任意序列的模板题

最新文章

热门文章

巴特西

hdu 1814 2-sat 输出字典最小的和任意序列的 模板题

最新文章

热门文章

hdu 1814 2-sat 输出字典最小的和任意序列的模板题