POJ 3207 Ikki's Story IV(2-sat)

Description

N个点按顺序排列在一个圆环上，要连接M条边，可从圈内连，可从圈外连，问能否实现各边不相交

2-sat

什么是2-SAT呢？就是

①有一些集合，(对应此题中有一些边)

②每个集合中有且仅有两个元素，(某条边是从圈内连or从圈外连)

③两个元素必须且只能选一个，(从圈内连或者从圈外连，二选一)

④集合间的元素存在一定的选择关系，(边不能相交)

求解可行性及可行方案。

算法过程

1、连边

2、跑Tarjan

3、判可行性，即同一集合中的两个点是否同属一个强连通块

(若不求可行方案，到此步即可)

4、缩点建新图，连反边

5、拓扑序，若当前点没有被访问过，则选择该点，不选择其另外的点

Analyze

对于此题，连线对应区间如果相交，那么两线不能同时在圈内或同时在圈外

Code

#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

stack<int> st;
vector<int> v[2005];
int n, m, t, num;///num:强连通分量(连通块)的个数,缩点后点的个数

bool vis[2105];///该点是否访问过
int inst[2105];///该点是否在栈中

int time[2105];///i点第一次被访问的时间
int low[2105];///i点所在强连通分量子图中第一个被搜到的点的time值

int ltt[2105];///i点属于第几个强连通分量(0表示不属于任何一个)

int l[2005], r[2005];

void init()///只一组数据无需init()
{
    t = num = 0;
    memset(vis, 0, sizeof(vis));
    memset(inst, 0, sizeof(inst));
    memset(time, 0, sizeof(time));
    memset(low, 0, sizeof(low));
    memset(ltt, 0, sizeof(ltt));
}

void Trajan(int x)///搜索x点及其子树
{
    int temp;
    st.push(x);
    inst[x] = vis[x] = 1;
    low[x] = time[x] = ++t;
    for(int i = 0; i < v[x].size(); i++)
    {
        temp = v[x][i];
        if(vis[temp] == 0)
        {
            Trajan(temp);
            low[x] = min(low[x], low[temp]);
        }
        else if(inst[temp] == 1)///成环时
            low[x] = min(low[x], time[temp]);
        else///点temp访问过却不在当前栈里：属于已发现的强连通分量
            continue;///这两个不能合二为一的原因：只有从此指彼的单向路
    }
    if(low[x] == time[x])
    {
        num++;///找到第num个强连通分量
        while(!st.empty())
        {
            temp = st.top();
            st.pop();
            ltt[temp] = num;///temp结点属于第num个强连通分量
            inst[temp] = 0;
            if(temp == x)
                break;
        }
    }
}

///强连通分量内元素个数最少为1(该元素本身)
///这意味着每个元素都有从属的强连通分量

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d", &l[i], &r[i]);
        l[i]++, r[i]++;///初始化涉及0,尽量避开使用下标0
        if(l[i] > r[i])
            swap(l[i], r[i]);
    }

    ///i j 是两条冲突线，不能同时连
    for(int i = 0; i < m; ++i)
        for(int j = i + 1; j < m; ++j)
            if((l[i] <= l[j] && r[i] >= l[j] && r[i] <= r[j])
                    || (l[j] <= l[i] && r[j] >= l[i] && r[j] <= r[i]))
            {
                ///① i  and  j'
                v[i].push_back(j + m);///i内j外
                v[j + m].push_back(i);///j外i内
                ///② i'  and  j
                v[i + m].push_back(j);///i外j内
                v[j].push_back(i + m);///j内i外
            }

    n = 2 * m;
    ///对所有点遍历，若未被访问过，就进行一遍Trajan
    for(int i = 1; i <= n; ++i)
        if(!vis[i])
            Trajan(i);

    bool flag = 1;
    for(int i = 1; i <= m; ++i)
        if(ltt[i] == ltt[i + m])
        {
            flag = 0;
            break;
        }
    if(flag)
        cout << "panda is telling the truth...\n";
    else
        cout << "the evil panda is lying again\n";
    return 0;
}