搜索，CF 1666L - Labyrinth

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

L - Labyrinth

二、解题报告

1、思路分析

考虑 从 s出发，搜索到 t，然后从t 沿着反向边一路往上走，不经过s -> t路径上的点最终到达s，那么说明找到了 两条首尾相同且不相交路径

如下图，黑色为正向边路径，红色为反向边路径

考虑从 s 开始dfs，额外添加参数 p 记录上一个点，rev 记录当前是否走逆向，如果当前为逆向那么后续只能逆向走

搜索的时候注意不能在s 就开始走逆向

以及 遇到搜索过的点，如果当前为逆向并且 该点为s，其实可以接着搜（找到了答案）

2、复杂度

时间复杂度： O(N + M)空间复杂度：O(N + M)

3、代码详解

 ​

#include <bits/stdc++.h>

// #define DEBUG

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

void solve() {
    int n, m, s;
    std::cin >> n >> m >> s;

    -- s;

    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (int i = 0; i < m; ++ i) {
        int u, v;
        std::cin >> u >> v;
        -- u, -- v;
        adj[u].emplace_back(v, 0);
        adj[v].emplace_back(u, 1);
    }

    std::vector<bool> vis(n);
    std::vector<int> nxt0(n, -1), nxt1(n, -1);

    auto dfs = [&](auto &&self, int u, int p, bool rev) -> bool {
        if (u == s && rev) {
            return true;
        }

        vis[u] = true;

        for (auto &[v, d] : adj[u]) {
            if (v == p) {
                continue;
            }

            if (vis[v] && !(v == s && d == 1)) {
                continue;
            }

            if (d == 0 && rev == 0) {
                nxt0[u] = v;
                if (self(self, v, u, 0)) {
                    return true;
                }
                nxt0[u] = -1;
            } else if(d == 1 && u != s) {
                nxt1[u] = v;
                if (self(self, v, u, 1)) {
                    return true;
                }   
                nxt1[u] = -1;
            }
        }

        vis[u] = false;

        return false;
    };


    if (dfs(dfs, s, -1, false)) {
        std::cout << "Possible\n";

        int cur = s;
        std::vector<int> path;
        while (cur != -1) {
            path.push_back(cur);
            cur = nxt0[cur];
        }

        std::cout << path.size() << '\n';
        for (int i = 0; i < path.size(); ++ i) {
            std::cout << path[i] + 1 << " \n"[i + 1 == path.size()];
        }

        cur = path.back();
        path.clear();
        while (cur != -1) {
            path.push_back(cur);
            cur = nxt1[cur];
        }

        std::reverse(path.begin(), path.end());

        std::cout << path.size() << '\n';
        for (int i = 0; i < path.size(); ++ i) {
            std::cout << path[i] + 1 << " \n"[i + 1 == path.size()];
        }
    } else {
        std::cout << "Impossible\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#ifdef DEBUG
    int START = clock();
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t = 1;
    // std::cin >> t;

    while (t --) {
        solve();
    }
#ifdef DEBUG
    std::cerr << "run-time: " << clock() - START << '\n';
#endif
    return 0;
}