round-trip

Round Trip

CSES medium

في دولة \(n\) مدينة و \(m\) طريقًا في الاتجاهين. صمّم رحلة دائرية: تبدأ في مدينة، وتمر بمدينتين أخريين أو أكثر، ثم تعود إلى مدينة البداية. يجب أن تكون كل المدن في وسط الرحلة مختلفة.

القيود:

\(1 \le n \le 10^5\)
\(1 \le m \le 2 \cdot 10^5\)
\(1 \le a, b \le n\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(m\).
الأسطر الـ \(m\) التالية: عددان صحيحان \(a\) و \(b\) — طريق بين المدينتين \(a\) و \(b\). كل طريق يربط مدينتين مختلفتين، ويوجد طريق واحد على الأكثر بين أي مدينتين.

المخرجات:

إذا وُجدت رحلة دائرية: أولًا عدد المدن \(k\) في الرحلة، ثم المدن الـ \(k\) بالترتيب (المدينة الأولى والأخيرة هي نفسها). إذا وُجد أكثر من رحلة فاطبع أيًّا منها.
وإلا: IMPOSSIBLE.

مثال:

الإدخال:

المخرجات:

4
3 5 1 3

الحل

الرحلة الدائرية هي دورة في الرسم البياني. لا توجد طرق مكررة، لذلك في كل دورة \(3\) مدن على الأقل، كما تطلب المسألة.

نشغّل البحث في العمق (DFS) ونتذكر أبا كل عقدة parent. عندما ترى DFS عند العقدة v جارًا to زارته من قبل وليس أبا v، نكون قد وجدنا دورة:

to سلف للعقدة v: لو كان to من أحفاد v، لوجدت DFS الحرف نفسه قبل ذلك، من جهة to؛
الدورة هي مسار أحرف الشجرة من to نزولًا إلى v، ويغلقها الحرف v–to.

نجمع الدورة بالمشي من v صعودًا عبر الآباء حتى نصل إلى to، ونضيف to في الطرفين. الترتيب معكوس مقارنة بترتيب DFS، لكن يمكن طباعة الرحلة الدائرية في أي من الاتجاهين.

إذا لم تجد DFS من كل عقدة غير مُزارة أي حرف كهذا، فالرسم البياني غابة والجواب IMPOSSIBLE.

التعقيد الزمني \(O(n + m)\).

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> g;
vector<int> parent;
vector<bool> visited;
int cycleStart = 0, cycleEnd = 0;

bool dfs(int v, int p) {
    visited[v] = true;
    parent[v] = p;

    for (int to : g[v]) {
        if (to == p) continue;  // the edge we came from
        if (visited[to]) {
            // an edge to an already visited node closes a cycle
            cycleStart = to;
            cycleEnd = v;
            return true;
        }
        if (dfs(to, v)) return true;
    }
    return false;
}

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

    int n, m;
    cin >> n >> m;

    g.resize(n + 1);
    parent.resize(n + 1);
    visited.resize(n + 1, false);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int v = 1; v <= n; v++) {
        if (!visited[v] && dfs(v, 0)) {
            // cycleStart is an ancestor of cycleEnd: collect the tree path between them
            vector<int> route;
            route.push_back(cycleStart);
            for (int u = cycleEnd; u != cycleStart; u = parent[u]) {
                route.push_back(u);
            }
            route.push_back(cycleStart);

            cout << route.size() << "\n";
            for (int u : route) {
                cout << u << ' ';
            }
            cout << "\n";
            return 0;
        }
    }

    cout << "IMPOSSIBLE\n";
}