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

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

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

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

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 10007#define pi acos(-1.0)#define MAXN 3005using 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 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。