message-route

Message Route

CSES easy

في شبكة \(n\) حاسوب و \(m\) اتصال. حاسوب أوليفي هو \(1\) وحاسوب مايا هو \(n\).

هل يستطيع أوليفي أن يرسل رسالة إلى مايا؟ إذا كان ذلك ممكنًا، فأوجد مسارًا فيه أقل عدد من الحواسيب.

القيود:

\(2 \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.

مثال:

الإدخال:

المخرجات:

3
1 4 5

الحل

الحواسيب عقد في رسم بياني غير موجّه، والاتصالات أحرفه. المسار الذي فيه أقل عدد من الحواسيب هو أقصر مسار من العقدة \(1\) إلى العقدة \(n\)، لذلك نشغّل البحث بالعرض (BFS) من العقدة \(1\)، كما في درس البحث بالعرض.

لنطبع المسار نفسه وليس طوله فقط، نخزّن لكل عقدة to العقدة parent[to] التي وصلت منها BFS إليها. ثم نمشي من \(n\) رجوعًا إلى \(1\) عبر الآباء ونعكس القائمة. أبو العقدة \(1\) هو \(0\)، وهذا يوقف المشي.

إذا لم تصل BFS إلى العقدة \(n\) أبدًا، فالجواب IMPOSSIBLE.

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

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

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

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

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

    vector<int> dist(n + 1, -1);
    vector<int> parent(n + 1, 0);
    queue<int> q;

    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int to : g[v]) {
            if (dist[to] != -1) continue;  // already visited
            dist[to] = dist[v] + 1;
            parent[to] = v;
            q.push(to);
        }
    }

    if (dist[n] == -1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    // walk back from n to 1 along the parents
    vector<int> path;
    for (int v = n; v != 0; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());

    cout << path.size() << "\n";
    for (int v : path) {
        cout << v << ' ';
    }
    cout << "\n";
}