HDOJ 1824 - Let's go home 简单构图2-set

一个队看作一个组.. 队长看成一个点..两个队员一起看作一个点...构造典型的2-sat模型...用tarjan判断可行性...

在tarjan里弹栈过程中忘记把instack置为false了...WA了好久..细心...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 10007
#define pi acos(-1.0)
#define MAXN 3005
using namespace std; 
struct node
{
       int x,y,next;
}line[10005]; 
int n,id[MAXN],dfn[MAXN],_next[MAXN],low[MAXN],tp[MAXN],_DfsIndex,tpnum;
bool instack[MAXN];
stack<int> mystack;
void addline(int x,int y,int m)
{
       line[m].next=_next[x],_next[x]=m;
       line[m].x=x,line[m].y=y;
}
void tarjan(int x)
{
       int k,y;
       dfn[x]=low[x]=++_DfsIndex;
       mystack.push(x);
       instack[x]=true;
       for (k=_next[x];k;k=line[k].next)
       {
              y=line[k].y;
              if (!dfn[y])
              {
                      tarjan(y);
                      low[x]=min(low[x],low[y]);
              }else 
              if (instack[y]) 
                      low[x]=min(low[x],dfn[y]);
       }
       if (dfn[x]==low[x])
       {
              tpnum++;
              do
              {
                      x=mystack.top();
                      mystack.pop();
                      instack[x]=false;
                      tp[x]=tpnum;
              }while (dfn[x]!=low[x]);
       }
       return;
}
bool judge()
{
       int i;
       for (i=0;i<n;i++)
           if (tp[i<<1]==tp[(i<<1)|1]) return false;
       return true;
}
int main()
{    
       int i,m; 
       while (~scanf("%d%d",&n,&m))
       {  
               for (i=0;i<n;i++)
               {
                        int c,a,b;
                        scanf("%d%d%d",&c,&a,&b);
                        id[c]=i<<1;
                        id[a]=id[b]=(i<<1)|1;
               }  
               memset(_next,0,sizeof(_next));
               for (i=0;i<m;i++)
               {
                        int x,y;
                        scanf("%d%d",&x,&y);
                        addline(id[x],id[y]^1,i<<1);
                        addline(id[y],id[x]^1,(i<<1)|1);
               }  
               memset(dfn,0,sizeof(dfn));
               memset(instack,false,sizeof(instack));
               while (!mystack.empty()) mystack.pop(); 
               _DfsIndex=tpnum=0; 
               for (i=0;i<(n<<1);i++)
                   if (!dfn[i]) tarjan(i);
               if (judge()) printf("yes\n");
                      else  printf("no\n");
               
       }
       return 0;
}