算法笔记--2-sat

强连通分量的应用，详见《挑战程序设计》P324

模板（2019.7）：

namespace two_sat {

    int dfn[M*], low[M*], cnt, stk[M*], top, cmp[M*], tot, n;

    bool vis[M*];

    vector<int> g[M*];

    void init(int sz) {

        n = sz;

    }

    void add(int u, int v) {

        g[u].pb(v);

    }

    void tarjan(int u) {

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

        stk[++top] = u;

        vis[u] = true;

        for (int v : g[u]) {

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

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

        }

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

            cmp[u] = ++tot;

            while(stk[top] != u) cmp[stk[top]] = tot, vis[stk[top--]] = false;

            vis[stk[top--]] = false;

        }

    }

    bool ck() {

        for (int i = ; i <= *n; ++i) if(!dfn[i]) tarjan(i);

        for (int i = ; i <= n; ++i) {

            if(cmp[i] == cmp[i+n]) return false;

        }

        return true;

    }

}

例题1：HDU Peaceful Commission

思路：强连通分量分解，看有没有两个同一个国家的代表在一个强连通分量里，如果有，就是NIE。这个不是关键，关键是怎么输出，输出还要用一下dfs，把所有能到达的点标记一下，顺便判断一下和之前有没有矛盾，有矛盾的话所有被标记的点又要重新标记回去。其实这道题可以不用强连通分量分解，直接dfs。

代码1（强连通分量分解+dfs）：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

int n,m,u,v;

const int N=2e4+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

bool vis[N];

bool vis1[N];

int cmp[N];

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<*n;i++)if(!vis[i])dfs(i);

    mem(vis,false);

    int k=;

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

void init()

{

    for(int i=;i<=*n;i++)g[i].clear(),rg[i].clear();

}

bool DFS(int u)

{

    vis[u]=true;

    vis1[u]=true;

    if(vis[u^])return false;

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

    {

        if(!vis[g[u][i]]&&!DFS(g[u][i]))return false;

    }

    return true;

}

void red(int u)

{

    vis1[u]=false;

    vis[u]=false;

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

    {

        if(vis1[g[u][i]])red(g[u][i]);

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    while(cin>>n>>m)

    {

        init();

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

        {

            cin>>u>>v;

            u--;

            v--;

            add_edge(u,v^);

            add_edge(v,u^);

        }

        int t=scc();

        bool flag=false;

        for(int i=;i<*n;i+=)if(cmp[i]==cmp[i+]){cout<<"NIE"<<endl;flag=true;break;}

        if(flag)continue;

        mem(vis,false);

        mem(vis1,false);

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

        {

            if(vis[i])

            {

                cout<<i+<<endl;

                continue;

            }

            else if(vis[i+])

            {

                cout<<i+<<endl;

                continue;

            }

            else

            {

                if(DFS(i))

                {

                    cout<<i+<<endl;

                }

                else

                {

                    red(i);

                    cout<<i+<<endl;

                    DFS(i+);

                }

            }

        }

    }

    return ;

}

代码2（dfs）:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

int n,m,u,v,tot;

const int N=2e4+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

bool vis[N];

int cmp[N];

int s[N];

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

/*void dfs(int u)

{

    vis[u]=true;

    for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=0;i<2*n;i++)if(!vis[i])dfs(i);

    mem(vis,false);

    int k=0;

    for(int i=vs.size()-1;i>=0;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}*/

void init()

{

    for(int i=;i<=*n;i++)g[i].clear(),rg[i].clear();

}

bool DFS(int u)

{

    if(vis[u^])return false;

    if(vis[u])return true;

    vis[u]=true;

    s[tot++]=u;

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

    {

        if(!DFS(g[u][i]))return false;

    }

    return true;

}

bool solve()

{

    mem(vis,false);

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

    {

        if(vis[i]||vis[i^])continue;

        tot=;

        if(!DFS(i))

        {

            while(tot)vis[s[--tot]]=false;

            if(!DFS(i^))return false;

        }

    }

    return true;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    while(cin>>n>>m)

    {

        init();

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

        {

            cin>>u>>v;

            u--;

            v--;

            add_edge(u,v^);

            add_edge(v,u^);

        }

        //int t=scc();

        if(solve())

        {

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

            if(vis[i])cout<<i+<<endl;

        }

        else cout<<"NIE"<<endl;

    }

    return ;

}

例题2：POJ 3207 Ikki's Story IV - Panda's Trick

思路：由于题目说每个点最多只能连一次，所以我直接用起点的坐标映射成它在圆内，+n后映射成它在圆外。不过这样求强连通时就要遍历每个点了，有点慢。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=2e3+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

vector<int>s;

bool vis[N];

int cmp[N];

int n,m,u,v;

int a[N];

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<*n;i++)if(!vis[i])dfs(i);

    int k=;

    mem(vis,false);

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    mem(a,-);

    cin>>n>>m;

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

    {

        cin>>u>>v;

        a[u]=v;

        a[v]=u;

        s.pb(u);

        s.pb(v);

    }

    sort(s.begin(),s.end());

    for(int i=;i<s.size();i++)

    {

        for(int j=i+;j<s.size();j++)

        {

            int l=min(s[i],a[s[i]]),r=max(s[i],a[s[i]]);

            int _l=min(s[j],a[s[j]]),_r=max(s[j],a[s[j]]);

            if((r>_l&&r<_r&&l<_l)||(l<_r&&l>_l&&r>_r))

            {

                add_edge(s[i],s[j]+n);

                add_edge(s[j],s[i]+n);

                add_edge(s[i]+n,s[j]);

                add_edge(s[j]+n,s[i]);

            }

        }

    }

    int t=scc();

    for(int i=;i<s.size();i++)

    if(cmp[s[i]]==cmp[s[i]+n])

    {

        cout<<"the evil panda is lying again"<<endl;

        return ;

    }

    cout<<"panda is telling the truth..."<<endl;

    return ;

}

例题3：POJ 3683 Priest John's Busiest Day

思路：大白书上的是输出拓扑序大的，不懂，留坑。

补坑：拓扑序大的没有边连向拓扑序小的强联通，所以不会产生矛盾。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=2e3+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

bool vis[N];

int cmp[N];

int n,m,u,v;

int S[N],T[N],D[N];

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<*n;i++)if(!vis[i])dfs(i);

    int k=;

    mem(vis,false);

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

void init()

{

    for(int i=;i<=n;i++)g[i].clear(),rg[i].clear();

}

void solve()

{

    mem(vis,false);

}

int main()

{

    int a,b,c,d;

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

    {

        init();

        for(int i=;i<n;i++)

        {

            scanf("%d:%d %d:%d %d",&a,&b,&c,&d,&D[i]);

            S[i]=a*+b;

            T[i]=c*+d;

        }

        for(int i=;i<n;i++)

        {

            for(int j=i+;j<n;j++)

            {

                if(min(S[i]+D[i],S[j]+D[j])>max(S[i],S[j]))add_edge(i,n+j),add_edge(j,n+i);

                if(min(T[i],T[j])>max(T[i]-D[i],T[j]-D[j]))add_edge(n+j,i),add_edge(n+i,j);

                if(min(T[i],S[j]+D[j])>max(T[i]-D[i],S[j]))add_edge(n+i,n+j),add_edge(j,i);

                if(min(T[j],S[i]+D[i])>max(T[j]-D[j],S[i]))add_edge(i,j),add_edge(n+j,n+i);

            }

        }

        int t=scc();

        bool flag=false;

        for(int i=;i<n;i++)if(cmp[i]==cmp[i+n]){

            flag=true;

            break;

        }

        if(flag)printf("NO\n");

        else

        {

            printf("YES\n");

            for(int i=;i<n;i++)

            {

                if(cmp[i]>cmp[n+i])

                printf("%02d:%02d %02d:%02d\n",S[i]/,S[i]%,(S[i]+D[i])/,(S[i]+D[i])%);

                else printf("%02d:%02d %02d:%02d\n",(T[i]-D[i])/,(T[i]-D[i])%,T[i]/,T[i]%);

            }

        }

    }

    return ;

}

例题4：POJ 3678 Katu Puzzle

思路：一开始看起来很复杂，其实只要建好边就好了。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=2e3+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

vector<int>s;

bool vis[N];

int cmp[N];

int n,m,u,v;

int a[N];

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<*n;i++)if(!vis[i])dfs(i);

    int k=;

    mem(vis,false);

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

void init()

{

    for(int i=;i<=*n;i++)g[i].clear(),rg[i].clear();

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int a;

    string t;

    while(cin>>n>>m)

    {

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

        {

            cin>>u>>v>>a>>t;

            if(t[]=='A')

            {

                if(a==)

                {

                    add_edge(u,v);

                    add_edge(v,u);

                    add_edge(u+n,u);

                    add_edge(v+n,v);

                }

                else

                {

                    add_edge(u,v+n);

                    add_edge(v,u+n);

                }

            }

            else if(t[]=='O')

            {

                if(a==)

                {

                    add_edge(u+n,v);

                    add_edge(v+n,u);

                }

                else

                {

                    add_edge(u+n,v+n);

                    add_edge(v+n,u+n);

                    add_edge(u,u+n);

                    add_edge(v,v+n);

                }

            }

            else if(t[]=='X')

            {

                if(a==)

                {

                    add_edge(u,v+n);

                    add_edge(v,u+n);

                    add_edge(v+n,u);

                    add_edge(u+n,v);

                }

                else

                {

                    add_edge(u,v);

                    add_edge(v,u);

                    add_edge(v+n,u+n);

                    add_edge(u+n,v+n);

                }

            }

        }

        scc();

        bool flag=false;

        for(int i=;i<n;i++)

        if(cmp[i]==cmp[i+n]){

            flag=true;

            break;

        }

        if(flag)cout<<"NO"<<endl;

        else cout<<"YES"<<endl;

    }

    return ;

}

例题5：POJ 3648 Wedding

思路：与例1相同，不过要建一条0号新娘和他新郎的边，这样只会选出新郎那一边的人。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

bool vis[N];

int cmp[N];

int s[N];

int n,m,u,v;

int tot=;

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<*n;i++)if(!vis[i])dfs(i);

    mem(vis,false);

    int k=;

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

void init()

{

    for(int i=;i<=*n;i++)g[i].clear(),rg[i].clear();

}

bool DFS(int u)

{

    if(u<n&&vis[u+n])return false;

    if(u>=n&&vis[u-n])return false;

    if(vis[u])return true;

    vis[u]=true;

    s[tot++]=u;

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

    {

        if(!DFS(g[u][i]))return false;

    }

    return true;

}

bool solve()

{

    mem(vis,false);

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

    {

        if(vis[i])continue;

        if(i>=n&&vis[i-n])continue;

        if(i<n&&vis[i+n])continue;

        tot=;

        if(!DFS(i))

        {

            while(tot)vis[s[--tot]]=false;

            if(i<n&&!DFS(i+n))return false;

            if(i>=n&&!DFS(i-n))return false;

        }

    }

    return true;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    string s1,s2;

    while(cin>>n>>m)

    {

        if(n==&&m==)break;

        init();

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

        {

            cin>>s1>>s2;

            int t=;

            for(int j=;j<s1.size();j++)

            {

                if(''<=s1[j]&&s1[j]<='')t=t*+s1[j]-'';

                else

                {

                    if(s1[j]=='w')

                    {

                        u=t;

                    }

                    else

                    {

                        u=n+t;

                    }

                }

            }

            t=;

            for(int j=;j<s2.size();j++)

            {

                if(''<=s2[j]&&s2[j]<='')t=t*+s2[j]-'';

                else

                {

                    if(s2[j]=='w')

                    {

                        v=t;

                    }

                    else

                    {

                        v=n+t;

                    }

                }

            }

            if(v<n)add_edge(u,v+n);

            else add_edge(u,v-n);

            if(u<n)add_edge(v,u+n);

            else add_edge(v,u-n);

        }

        add_edge(,n);

        int t=scc();

        bool flag=false;

        for(int i=;i<n;i++)

        {

            if(cmp[i]==cmp[i+n])

            {

                flag=true;

                break;

            }

        }

        if(flag)

        {

            cout<<"bad luck"<<endl;

        }

        else

        {

            tot=;

            mem(vis,false);

            solve();

            for(int i=;i<n;i++)

            {

                if(vis[i])cout<<i<<"h";

                else cout<<i<<"w";

                if(i!=n-)cout<<' ';

            }

            cout<<endl;

        }

    }

    return ;

}

例题6：Codeforces 468B - Two Sets

思路：如果x在a集合中，那么a-x不存在的话，x一定在b集合（x在a==>x在b）；如果a-x存在，那么有(原命题：x在a==>a-x在a，逆否命题：a-x在b==>x在b)，同理，x在b集合中也是一样的。建边建好了就可以输出拓扑序大的了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=2e5+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

int belong[N]={};

bool vis[N];

int cmp[N];

int s[N];

int n;

int tot=;

struct node

{

    int v,id;

    bool operator < (node t)const

    {

        return v<t.v;

    }

}a[N];

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<*n;i++)if(!vis[i])dfs(i);

    mem(vis,false);

    int k=;

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

/*bool DFS(int u)

{

    if(u<n&&vis[u+n])return false;

    if(u>=n&&vis[u-n])return false;

    if(vis[u])return true;

    vis[u]=true;

    s[tot++]=u;

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

    {

        if(!DFS(g[u][i]))return false;

    }

    return true;

}

bool solve()

{

    mem(vis,false);

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

    {

        if(vis[i])continue;

        if(i>=n&&vis[i-n])continue;

        if(i<n&&vis[i+n])continue;

        tot=0;

        if(!DFS(i))

        {

            while(tot)vis[s[--tot]]=false;

            if(i<n&&!DFS(i+n))return false;

            if(i>=n&&!DFS(i-n))return false;

        }

    }

    return true;

} */

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int A,B;

    cin>>n>>A>>B;

    for(int i=;i<n;i++)cin>>a[i].v,a[i].id=i;

    sort(a,a+n);

    for(int i=;i<n;i++)

    {

        //bool flag=false;

        int t=lower_bound(a,a+n,node{A-a[i].v,})-a;

        if(t!=n&&a[t].v==A-a[i].v)

        {

            //flag=true;

            add_edge(a[i].id,a[t].id);

            add_edge(a[t].id+n,a[i].id+n);

        }

        else

        {

            add_edge(a[i].id,a[i].id+n);

        }

        t=lower_bound(a,a+n,node{B-a[i].v,})-a;

        if(t!=n&&a[t].v==B-a[i].v)

        {

            //flag=true;

            add_edge(a[i].id+n,a[t].id+n);

            add_edge(a[t].id,a[i].id);

        }

        else

        {

            add_edge(a[i].id+n,a[i].id);

        }

        /*if(!flag)

        {

            cout<<"NO"<<endl;

            return 0;

        }*/

    }

    int t=scc();

    for(int i=;i<n;i++)

    if(cmp[i]==cmp[i+n])

    {

        cout<<"NO"<<endl;

        return ;

    }

    cout<<"YES"<<endl;

    //solve();

    for(int i=;i<n;i++)if(cmp[i]>cmp[i+n])cout<<<<' ';else cout<<<<' ';

    cout<<endl;

    return ;

}

代码复杂了，因为所有数不同，所以数可以直接映射成下标。

例题7：Codeforces 867E National Property

思路：学会建矛盾边（自己的叫法）。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=2e5+;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

vector<int>a[N];

bool vis[N];

int cmp[N];

int n,m;

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<=*m;i++)if(!vis[i])dfs(i);

    mem(vis,false);

    int k=;

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

void init()

{

    for(int i=;i<=*m;i++)g[i].clear(),rg[i].clear();

    for(int i=;i<n;i++)a[i].clear();

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int t,b;

    while(cin>>n>>m)

    {

        init();

        for(int i=;i<n;i++)

        {

            cin>>t;

            for(int j=;j<t;j++)cin>>b,a[i].pb(b);

        }

        bool f=false;

        for(int i=;i<n-;i++)

        {

            //cout<<a[i].size()<<endl;

            if(a[i].size()<=a[i+].size())

            {

                for(int j=;j<a[i].size();j++)

                {

                    if(a[i][j]<a[i+][j])

                    {

                         add_edge(a[i][j],a[i+][j]);

                         add_edge(a[i+][j]+m,a[i][j]+m);

                         break;

                    }

                    else if(a[i][j]>a[i+][j])

                    {

                         add_edge(a[i][j],a[i][j]+m);

                         add_edge(a[i+][j]+m,a[i+][j]);

                         add_edge(a[i][j]+m,a[i+][j]);

                         add_edge(a[i+][j],a[i][j]+m);

                         break;

                    }

                }

            }

            else

            {

                bool flag=false;

                for(int j=;j<a[i+].size();j++)

                {

                    if(a[i][j]<a[i+][j])

                    {

                        flag=true;

                         add_edge(a[i][j],a[i+][j]);

                         add_edge(a[i+][j]+m,a[i][j]+m);

                         break;

                    }

                    else if(a[i][j]>a[i+][j])

                    {

                        flag=true;

                         add_edge(a[i][j],a[i][j]+m);

                         add_edge(a[i+][j]+m,a[i+][j]);

                         add_edge(a[i][j]+m,a[i+][j]);

                         add_edge(a[i+][j],a[i][j]+m);

                         break;

                    }

                }

                if(!flag)

                {

                    f=true;

                    break;

                }

            }

        }

        if(f)cout<<"No"<<endl;

        else

        {

            //cout<<1<<endl;

            scc();

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

            {

                if(cmp[i]==cmp[i+m])

                {

                    f=true;

                //    cout<<i<<endl;

                    break;

                }

            }

            if(f)cout<<"No"<<endl;

            else

            {

                cout<<"Yes"<<endl;

                int cnt=;

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

                if(cmp[i]<cmp[i+m])cnt++;

                cout<<cnt<<endl;

                for(int i=;i<=m;i++)if(cmp[i]<cmp[i+m])cout<<i<<' ';

                cout<<endl;

            }

        }

    }

    return ;

}

总结：

关于建边：如果x一定不能选，那么建一条x连向！x的边。

关于输出：2-sat问题的输出如果没有限制条件，那么直接输出拓扑序大的一组答案，如果有限制条件，DFS染色标记后再输出答案。

巴特西

算法笔记--2-sat

最新文章

热门文章