CF 97E 题解

admin 2021-08-31 PM 98℃ 0条

题目链接

分析

首先比较显然的想法是随便找一棵生成树,然后 $u$ 和 $v$ 之间存在奇数长度路径当且仅当满足下列两个条件之一:

  • $u$ 和 $v$ 在生成树上的路径长度为奇数
  • $u$ 和 $v$ 在生成树上的路径中,存在一条边在原图中的一个奇环中。

只要提前知道生成树上的每一条边是否在奇环中,然后在树上就随便用什么算法处理都行。

如何判断一条边是否在奇环中呢?

首先,两个点双之间肯定没有环。

而如果一个点双中存在一个奇环,那么这个点双中任意一条边都在一个奇环中!

选取两个奇环上的两点 $x,y$,向外扩展出一条路径:

graph.png

比如上面这张图中,奇环为 1-4-5,选取 $x=1,y=4$,向外扩展出路径 1-2-3-4。

一定存在一条同时经过 $x$ 和 $y$ 的奇环。所以,存在两条 $x$ 到 $y$ 的路径,一条长度为偶数,一条长度为奇数。

新扩展出的路径一定可以和着两条路径中的一条组成一个奇环。在上图中,这个环是 1-2-3-4-5-1。

故一条边在奇环中,当且仅当它所在的点双中存在奇环。

可以在 Tarjan 时找到点双中的所有边,采用二分图的方式判断奇环。

时间复杂度线性。

update: 解决

判断的时候应该要把 V-DCC 单独拿出来建新图判断,暴力遍历出边可以被卡成平方,下面是数据生成器:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int main()
{
    freopen("CF97E.in", "w", stdout);
    puts("66667 99999");
    for (int i = 1; i <= 33333; i++)
        printf("1 %d\n1 %d\n%d %d\n", i * 2, i * 2 + 1, i * 2, i * 2 + 1);
    puts("0");
    return 0;
}

这份代码会生成 33333 个三元环。

被 hack 的题解:

下面给出(我认为)正确的实现:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100005, M = 200005, LOG = 17;
int n, m, q;
int head[N], ver[M], nxt[M], tot = 1, v[N];
int _head[N], _ver[M], _nxt[M], _tot = 1;
int dfn[N], low[N], dfsNum, stkNode[N], topNode, stkEdge[M >> 1][3], topEdge, color[N], checkNum;
int dep[N], fa[N][LOG], rt[N], root;
bool ok[M >> 1], flag[N][LOG], vis[M >> 1];

void addedge(int x, int y)
{
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void _addedge(int x, int y)
{
    _ver[++_tot] = y, _nxt[_tot] = _head[x], _head[x] = _tot;
}

bool check(int cur)
{
    v[cur] = checkNum;
    for (int i = _head[cur]; i; i = _nxt[i])
    {
        int to = _ver[i];
        if (v[to] == checkNum)
        {
            if (color[to] == color[cur])
                return false;
            continue;
        }
        color[to] = 3 - color[cur];
        if (!check(to))
            return false;
    }
    return true;
}

void Tarjan(int cur)
{
    low[cur] = dfn[cur] = ++dfsNum, stkNode[++topNode] = cur;
    for (int i = head[cur]; i; i = nxt[i])
    {
        int curTop = topEdge, to = ver[i];
        if (!vis[i >> 1])
            vis[i >> 1] = true, topEdge++, stkEdge[topEdge][0] = (i >> 1), stkEdge[topEdge][1] = cur,
                     stkEdge[topEdge][2] = to;
        if (!dfn[to])
        {
            Tarjan(to);
            low[cur] = min(low[cur], low[to]);
            if (low[to] >= dfn[cur])
            {
                _head[cur] = _head[to] = 0, _tot = 1;
                while (stkNode[topNode] != to)
                    _head[stkNode[topNode]] = 0, topNode--;
                topNode--;
                for (int j = curTop + 1; j <= topEdge; j++)
                    _addedge(stkEdge[j][1], stkEdge[j][2]);
                color[cur] = 1, checkNum++;
                if (!check(cur))
                    for (int j = curTop + 1; j <= topEdge; j++)
                        ok[stkEdge[j][0]] = true;
                topEdge = curTop;
            }
        }
        else
            low[cur] = min(low[cur], dfn[to]);
    }
}

void Tarjan()
{
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            Tarjan(i);
}

void dfs(int cur)
{
    rt[cur] = root;
    for (int i = head[cur]; i; i = nxt[i])
    {
        int to = ver[i];
        if (rt[to])
            continue;
        dep[to] = dep[cur] + 1, fa[to][0] = cur, flag[to][0] = ok[i >> 1];
        for (int j = 1; j < LOG; j++)
            fa[to][j] = fa[fa[to][j - 1]][j - 1], flag[to][j] = flag[to][j - 1] || flag[fa[to][j - 1]][j - 1];
        dfs(to);
    }
}

bool query(int x, int y)
{
    if (rt[x] != rt[y] || x == y)
        return false;
    if ((dep[x] + dep[y]) & 1)
        return true;
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = LOG - 1; i >= 0; i--)
        if (dep[fa[x][i]] >= dep[y])
        {
            if (flag[x][i])
                return true;
            x = fa[x][i];
        }
    if (x == y)
        return false;
    for (int i = LOG - 1; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
        {
            if (flag[x][i] || flag[y][i])
                return true;
            x = fa[x][i], y = fa[y][i];
        }
    return flag[x][0] || flag[y][0];
}

template<class T>
void read(T &ret)
{
    ret = 0;
    char ch = getchar(), flag = 0;
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-')
        ch = getchar(), flag = 1;
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    if (flag)
        ret = -ret;
}

int main()
{
    read(n), read(m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        read(x), read(y);
        addedge(x, y), addedge(y, x);
    }
    Tarjan();
    for (int i = 1; i <= n; i++)
    {
        if (rt[i])
            continue;
        for (int j = 0; j < LOG; j++)
            fa[i][j] = 1;
        root = i;
        dfs(i);
    }
    read(q);
    while (q--)
    {
        int x, y;
        read(x), read(y);
        if (query(x, y))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

非特殊说明,本博所有文章均为博主原创。

评论啦~