poj3905 2sat!

这次已经不是2sat的问题了，相信2sat已经不是问题了，最后一题2sat，竟然跪在输入上！

千万注意scanf(%c)!读入！！！！有空格也读啊！！！读入+ -一定要用字符读啊？？笨死算了！被人水死！为人岂自甘下流栽！！好好努力！

对于+1 -1 这样带符号的，直接%d读入判断符号即可啊！切记！！！

#include<iostream>   //1688MS 第一页有木有！

#include<cstring>

#include<cstdio>

#include<stack>

#include<vector>

using namespace std;

const int MAX=2100;

int n,m;int times=0;

int low[MAX];int dfn[MAX];int visited[MAX];int isinstack[MAX];stack<int>s;

int scc[MAX];int numblock=0;

vector<vector<int> >edges(MAX);  //图

void clear()

{

    times=numblock=0;

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

    {

        visited[i]=dfn[i]=low[i]=isinstack[i];

        scc[i]=-1;

        edges[i].clear();

    }

}

void tarjan(int u)       //dfs

{

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

    isinstack[u]=1;

    s.push(u); int len=edges[u].size();

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

       {

           int v=edges[u][i];

           if(visited[v]==0)

           {

               visited[v]=1;

               tarjan(v);

               if(low[u]>low[v])low[u]=low[v];

           }

           else if(isinstack[v]&&dfn[v]<low[u])

              low[u]=dfn[v];

       }

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

    {

        numblock++;int cur;

        do

        {

            cur=s.top();s.pop();

            isinstack[cur]=0;

            scc[cur]=numblock;

        }while(cur!=u);

    }

}

bool check()

{

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

         if(visited[i]==0)

         {

             visited[i]=1;

             tarjan(i);

         }

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

    {

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

            return 0;

    }

     return 1;

}

void readin()

{

    int temp1;int temp2;

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

    {

       scanf("%d%d",&temp1,&temp2);  //对于+1 -1 这样带符号的，直接读入啊！！！切记！

        if(temp1>0&&temp2>0)

          {

               edges[temp1*2-1].push_back(temp2*2-2);

               edges[temp2*2-1].push_back(temp1*2-2);

          }

        else   if(temp1>0&&temp2<0)

          {

              temp2=-temp2;

               edges[temp1*2-1].push_back(temp2*2-1);

               edges[temp2*2-2].push_back(temp1*2-2);

          }

       else   if(temp1<0&&temp2>0)

          {

              temp1=-temp1;

               edges[temp1*2-2].push_back(temp2*2-2);

               edges[temp2*2-1].push_back(temp1*2-1);

          }

       else   if(temp1<0&&temp2<0)

          {

              temp1=-temp1;temp2=-temp2;

               edges[temp1*2-2].push_back(temp2*2-1);

               edges[temp2*2-2].push_back(temp1*2-1);

          }

    }

}

int main()

{

   // ios::sync_with_stdio(false);   //据说用了这句话，统一用cin>>，它的速度会变快！

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

    {

        clear();

        readin();

        if(check())

            printf("1\n");

        else

            printf("0\n");

    }

    return 0;

}

巴特西

poj3905 2sat!

最新文章

热门文章