2-SAT問題-拓撲列可行解

由对称性解2-SAT问题 - 博客园

演算法筆記

一、建立有向圖。
二、尋找所有Strongly Connected Component。
三、收縮每個Strongly Connected Component，成為有向無環圖DAG。
四、尋找縮圖的Topological Ordering。
五、在縮圖上，以Topological Ordering的反序，列出解。

* N个集团，每个集团2个人(0<=ni<2n p="p">

* 且每个集团只能选出一个人。如果两人有矛盾，他们不能同时被选中

* 问最多能选出多少人並列出

sample input:
3 4 (N M) (N組人M組條件)
1 2 (第1組)
3 4
5 6 (第3組)
1 3 (第1條件: 1不與3同時選上)
1 5
2 3
2 4

//reference: 演算法筆記 http://www.csie.ntnu.edu.tw/~u91029/SimulationModeling.html#a6
#include<stdio.h>
#include<string.h>
#include<iostream>
#define DBG 1

using namespace std;
int visit[20],map[20][20];
int sat[20];        
int finish[20], scc[20], n, N;
int f[20],x[20],y[20];

void DFS1(int i)
{
    visit[i] = true;
    for (int j=0; j<N+N; ++j)
        if (map[i][j] && !visit[j])
            DFS1(j);
    finish[n++] = i;
}
void DFS2(int i)
{
    scc[i] = n;
    if(DBG)printf("scc[%d]=%d\n",i+1,n);
    visit[i] = true;
    for (int j=0; j<N+N; ++j)
        if (map[j][i] && !visit[j]){
            DFS2(j);
        }
}
void two_satisfiability()
{
    n = 0;  // 時刻
    memset(visit, false, sizeof(visit));
    for (int i=0; i<N; ++i)
        if (!visit[i])
            DFS1(i);
            
    memset(visit, false, sizeof(visit));
    for (int k=N-1; k>=0; --k)
    {
        
        int i = finish[k];
        if (!visit[i])
            DFS2(i), n++;
    }
    // 檢查是否有解，無解則立即結束。
    for (int i=0; i<N; ++i)
        if (scc[i] == scc[f[i]])
            return;

    // 找出一組解
    memset(sat, 0, sizeof(sat));
    for (int k=0; k<N; ++k)
    {
        int i = finish[k];
        if (!sat[scc[i]])
        {
            sat[scc[i]] = 1;
            sat[scc[f[i]]] = 2;
        }
    }
    // 印出一組解
    for (int i=0; i<N; ++i)
        if (sat[scc[i]] == 1)
            cout << i+1 <<endl;
}

int main(){
    int m;
    while (scanf("%d%d",&N,&m)!=EOF && N+m){
        int p,q;
        for (int i=0;i<N;i++){
            scanf("%d%d",&p,&q),p--,q--;
            f[p]=q,f[q]=p;
        }
        for (int i=0;i<m;i++) scanf("%d%d",&p,&q),p--,q--,x[i]=p,y[i]=q;
        for (int i=0;i<m;i++){
            map[x[i]][f[y[i]]]=map[y[i]][f[x[i]]]=1;
        }
        N*=2;
        two_satisfiability();
    }
    return 0;
}