poj3207

poj3207

题意

平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，

比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。

给你的信息中，每个点最多只会连接的一条边。问能不能连接这m条边，

使这些边都不相交。

分析

建图 见代码， 2-SAT模板

code

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int INF = 1e9;

const int MAXN = 2e3 + 5;

int n, m; // 点、边

int vis[MAXN];

int flag[MAXN]; // 所属强连通分量的拓扑序

vector<int> G[MAXN], rG[MAXN];

vector<int> vs; // 后序遍历顺序的顶点列表

void addedge(int x, int y)

{

    G[x].push_back(y);  // 正向图

    rG[y].push_back(x); // 反向图

}

void dfs(int u)

{

    vis[u] = 1;

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

    {

        int v = G[u][i];

        if(!vis[v]) dfs(v);

    }

    vs.push_back(u);

}

void rdfs(int u, int k)

{

    vis[u] = 1;

    flag[u] = k;

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

    {

        int v = rG[u][i];

        if(!vis[v]) rdfs(v, k);

    }

}

int scc() // 强连通分量的个数

{

    vs.clear();

    memset(vis, 0, sizeof vis);

    for(int i = 1; i <= n; i++) //  [1...n]

        if(!vis[i]) dfs(i);

    memset(vis, 0, sizeof vis);

    int k = 0;

    for(int i = vs.size() - 1; i >= 0; i--)

        if(!vis[vs[i]]) rdfs(vs[i], k++);

    return k;

}

struct node { int s, t; } a[MAXN];

bool judge()

{

    int N = n;

    n = 2 * n;

    scc();

    for(int i = 1; i <= N; i++)

        if(flag[i] == flag[i + N])

            return false;

    return true;

}

int main()

{

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

    {

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

        {

            int s, t; s++; t++;

            if(s > t) swap(s, t);

            scanf("%d%d", &a[i].s, &a[i].t);

        }

        memset(G, 0, sizeof G);

        memset(rG, 0, sizeof rG);

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

        {

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

            {

                if((a[i].s > a[j].s && a[i].s < a[j].t && a[i].t > a[j].t)

                    || (a[j].s > a[i].s && a[j].s < a[i].t && a[j].t > a[i].t))

                {

                    addedge(i, j + n);

                    addedge(j, i + n);

                    addedge(i + n, j);

                    addedge(j + n, i);

                }

            }

        }

        puts(judge() ? "panda is telling the truth..." : "the evil panda is lying again");

    }

    return 0;

}