526互联

[ABC318G] Typical Path Problem 题解

发布时间 2023-09-03 20:22:11作者: User-Unauthorized

题意

给定一个 \(N\) 个节点和 \(M\) 条边组成的简单无向联通图，给定三个节点 \(A,B,C\)，求是否存在一条简单路径满足 \(A \rightarrow B \rightarrow C\)。

（\(3 \le N, M \le 2 \times 10^5\)）。

题解

因为简单路径要求每个节点至多经过一次，故不存在合法的简单路径当且仅当存在一个割点同时存在于路径 \(A \rightarrow B\) 和路径 \(B \rightarrow C\) 上。故建立圆方树后跑两遍 \(\tt{DFS}\) 即可，第一遍标记路径 \(A \rightarrow B\) 上的点，第二遍检查路径 \(B \rightarrow C\) 上是否有被标记且为割点的点。

总复杂度 \(\mathcal{O}(N + M)\)，可以通过本题。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;

valueType N, M;
valueType A, B, C;

ValueVector dfn, low;
ValueMatrix G, tree, dcc;
bitset cut, path;
std::stack<valueType> S;

void tarjan(valueType x, valueType from) {
    static valueType time = 0;

    dfn[x] = low[x] = ++time;

    S.push(x);

    valueType son = 0;

    for (auto const &iter: G[x]) {
        if (iter == from)
            continue;

        if (!dfn[iter]) {
            ++son;

            tarjan(iter, x);

            low[x] = std::min(low[x], low[iter]);

            if (low[iter] >= dfn[x]) {
                cut[x] = true;

                dcc.emplace_back();
                dcc.back().emplace_back(x);

                int y;

                do {
                    y = S.top();
                    S.pop();
                    dcc.back().emplace_back(y);
                } while (y != iter);
            }
        } else {
            low[x] = std::min(low[x], dfn[iter]);
        }
    }

    if (from == 0 && son == 1)
        cut[x] = false;
}

void build() {
    for (valueType i = 0; i < dcc.size(); ++i) {
        valueType const x = N + i + 1;

        for (auto const &iter: dcc[i]) {
            tree[x].push_back(iter);
            tree[iter].push_back(x);
        }
    }
}

bool dfs(valueType x, valueType from, valueType TOP) {
    if (x == TOP)
        return path[x] = true;

    for (auto const &iter: tree[x]) {
        if (iter == from)
            continue;

        if (dfs(iter, x, TOP))
            return path[x] = true;
    }

    return path[x] = false;
}

bool check(valueType x, valueType from, valueType TOP, bool &result) {
    if (x == TOP)
        return true;

    for (auto const &iter: tree[x]) {
        if (iter == from)
            continue;

        if (check(iter, x, TOP, result)) {
            if (path[x] && cut[x])
                result = false;

            return true;
        }
    }

    return false;
}

int main() {
    std::cin >> N >> M;

    std::cin >> A >> B >> C;

    G.resize(N + 10);
    tree.resize(2 * N + 10);
    dfn.resize(N + 10, 0);
    low.resize(N + 10, 0);
    cut.resize(2 * N + 10, false);
    path.resize(2 * N + 10, false);

    for (valueType i = 0; i < M; ++i) {
        valueType u, v;

        std::cin >> u >> v;

        G[u].push_back(v);
        G[v].push_back(u);
    }

    tarjan(1, 0);

    build();

    dfs(A, 0, B);

    bool result = true;

    check(C, 0, B, result);

    if (result)
        std::cout << "Yes" << std::endl;
    else
        std::cout << "No" << std::endl;
}