Labyrinth

Created by LXC on Fri Jan 5 19:20:42 2024

https://codeforces.com/problemset/problem/1666/L

ranting: 1800

tag: dfs and similar, graphs

problem

有一个 $n$（$2 \le n \le 2 \cdot 10^5$）个点（编号为 $1,2,…,n$），$m$ （$0 \le m \le 2 \cdot 10^5$）条边的有向图，现在想找到两条路径，使得：

• 它们的起点都在一个给定的点上；
• 它们的终点在相同的点上（这个点可能是除起点外任意一个点）；
• 它们除起点和终点外，不能有重复的点；
• 每条路径不能经过重复的点。

现在给出这个图和起点，先输出是（Possible）否（Impossible）存在符合上述条件的两条路径。

如果存在，再输出：

• 每条路径分别经过几个点（包括起点、终点）；
• 这两条路径依次经过的点。

若不存在，不用再输出。

solution

dfs染色，我们把s点直接连接的点找出来，并以这些点作为dfs起点染上不同颜色，当dfs遇到一个节点是之前某次dfs染的颜色（不是当前dfs将要染的颜色），那么这个点就是两条路径的终点。

注意，s点直接连接的点可能已经染上了之前的颜色。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 200005
#define MOD 998244353
using namespace std;

vector<int> g[N], st;
int c[N];
int fa[N];

int dfs(int u, int id) {
    st.push_back(u);
    if (c[u]) {
        cout << "Possible\n";
        vector<int> p;
        int t = u;
        while (t)
            p.push_back(t), t = fa[t];
        reverse(p.begin(), p.end());
        cout << p.size() << "\n";
        for (auto i : p) {
            cout << i << " ";
        }
        cout << "\n";
        cout << st.size() << "\n";
        for (auto i : st) {
            cout << i << " ";
        }
        cout << "\n";
        return 1;
    }
    c[u] = id;
    for (auto v : g[u]) {
        if (c[v] == id)
            continue;
        if (dfs(v, id))
            return 1;
        fa[v] = u;
    }
    st.pop_back();
    return 0;
}

void sol() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }
    st.push_back(s);
    for (int i = 0; i < g[s].size(); i++) {
        c[s] = i + 1;
        if (dfs(g[s][i], i + 1))
            return;
        fa[g[s][i]] = s;
    }
    cout << "Impossible\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}