[洛谷P4782] [模板] 2-SAT 问题

NOIp后第一篇题解。

NOIp我考的很凉啊......

题目传送门

之前讲过怎么判断2-SAT是否存在解。

至于如何构造一组解：

我们想到对tarjan缩点后的图进行拓扑排序。

那么对于代表0状态的点和代表1状态的点，我们尽量取拓扑序大的，这样可以减少冲突。

然而我们并不需要拓扑排序QAQ

先tarjan出来的强连通分量一定是拓扑序较大的。

所以我们借用一下tarjan时候的dfn数组即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int hd[2000005],to[2000005],nx[2000005],ec;
 8 
 9 void edge(int af,int at)
10 {
11     to[++ec]=at;
12     nx[ec]=hd[af];
13     hd[af]=ec;
14 }
15 
16 int dfn[2000005],low[2000005],pc;
17 int gp[2000005],gc;
18 int st[2000005],in[2000005],tp;
19 
20 void tarjan(int p)
21 {
22     dfn[p]=low[p]=++pc;
23     st[++tp]=p;
24     in[p]=1;
25     for(int i=hd[p];i;i=nx[i])
26     {
27         if(!dfn[to[i]])tarjan(to[i]),low[p]=min(low[p],low[to[i]]);
28         else if(in[to[i]])low[p]=min(low[p],dfn[to[i]]);
29     }
30     if(low[p]==dfn[p])
31     {
32         gc++;
33         int np=0;
34         while(np!=p)
35         {
36             np=st[tp--];
37             in[np]=0;
38             gp[np]=gc;
39         }
40     }
41 }
42 
43 int main()
44 {
45     scanf("%d%d",&n,&m);
46     for(int i=1;i<=m;i++)
47     {
48         int p1,s1,p2,s2;
49         scanf("%d%d%d%d",&p1,&s1,&p2,&s2);
50         edge(p1+n*(s1^1),p2+n*s2);
51         edge(p2+n*(s2^1),p1+n*s1);
52     }
53     for(int i=1;i<=2*n;i++)
54         if(!dfn[i])tarjan(i);
55     int fl=1;
56     for(int i=1;i<=n;i++)
57     {
58         if(gp[i]==gp[i+n])
59         {
60             fl=0;
61             break;
62         }
63     }
64     if(fl)
65     {
66         printf("POSSIBLE
");
67         for(int i=1;i<=n;i++)
68         {
69             printf("%d ",gp[i]>gp[i+n]);
70         }
71     }
72     else printf("IMPOSSIBLE
");
73     return 0;
74 }

就这样。