P3209 平面图判定 做题记录

· · 个人记录

这种题我是非常讨厌的，你必须要知道平面图的性质才能做这道题，性质是：m<=3\times n+6(n\ge 3)，所以题目中 m\le 10000 的条件根本是假的，实际上它最多为 594。所以当 m 过大时，我们直接输出 NO 就行了。

然后我们来看 2-SAT 的做法：这道题搞清楚这个就跟这个一样，由于环上数字的顺序不是从小到大顺时针排的，但是我们仍然可以记录每个数字在环上的顺序 ord 然后来判断是否相交，另外这道题拆的元素是 m 不是 n，数组别开太小。
代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 40005
#define M 500005
using namespace std;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9')
        ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}

inline void write(ll x)
{
    static int top = 0, sta[39];
    if (x < 0)
        pr('-');
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

struct edge
{
    int v, next;
} e[M << 1];
int head[N], cnt;

inline void add(int u, int v)
{

    e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, a, bcc, top;
int x[N], y[N], dfn[N], low[N], num[N], vis[N], ord[N], stack[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1, stack[++top] = u;
    for (rnt i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        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])
    {
        bcc++;
        while (stack[top + 1] != u)
            num[stack[top]] = bcc, vis[stack[top--]] = 0;
    }
}

int main()
{
    int time = read();
    while (time--)
    {
        bool f = 1;
        n = read(), m = read();
        for (rnt i = 1; i <= m; i++)
            x[i] = read(), y[i] = read();
        for (rnt i = 1; i <= n; i++)
            a = read(), ord[a] = i;
        if (m > 3 * n - 6)
        {
            puts("NO");
            continue;
        }
        for (rnt i = 1; i <= m; i++)
            if (ord[x[i]] > ord[y[i]])
                swap(x[i], y[i]);
        for (rnt i = 2; i <= m; i++)
            for (rnt j = 1; j < i; j++)
                if ((ord[x[i]] < ord[x[j]] && ord[x[j]] < ord[y[i]] && ord[y[i]] < ord[y[j]]) || (ord[x[j]] < ord[x[i]] && ord[x[i]] < ord[y[j]] && ord[y[j]] < ord[y[i]]))
                    add(i, j + m), add(i + m, j), add(j, i + m), add(j + m, i);
        for (rnt i = 1; i <= 2 * m; i++)
            if (!dfn[i])
                tarjan(i);
        for (rnt i = 1; i <= m; i++)
            if (num[i] == num[i + m])
                f = 0;
        if (f)
            puts("YES");
        else
            puts("NO");
        for (rnt i = 1; i <= 2 * m; i++)
            dfn[i] = num[i] = vis[i] = head[i] = stack[i] = 0;
        bcc = cnt = top = 0;
    }
    return 0;
}