uniolympiads English

BFS και 0-1 BFS

Συντομότερες αποστάσεις σε γράφο χωρίς βάρη σε O(n+m)O(n + m). Με βάρη μόνο 0 και 1, το ίδιο με μια ουρά δύο άκρων.

Πότε

«Ελάχιστος αριθμός κινήσεων», «συντομότερη διαδρομή σε λαβύρινθο», «είναι ο γράφος διμερής;». Κάθε φορά που κάθε βήμα κοστίζει το ίδιο.

Η ιδέα

Η ουρά βγάζει τις κορυφές σε αύξουσα σειρά απόστασης: πρώτα όλες στην απόσταση dd, μετά όλες στην d+1d + 1. Γι' αυτό την πρώτη φορά που βλέπουμε μια κορυφή, η απόσταση που της δίνουμε είναι ήδη η τελική. Κάθε κορυφή μπαίνει στην ουρά μία φορά και κάθε ακμή εξετάζεται μία φορά (δύο σε μη κατευθυνόμενο γράφο).

Για να βρεις και τη διαδρομή, όχι μόνο το μήκος της, κράτα parent[v] = u τη στιγμή που ανακαλύπτεις το vv και ακολούθησε τους γονείς από το τέλος.

0-1 BFS. Με βάρη 0 ή 1, μια ακμή βάρους 0 δεν αλλάζει το «επίπεδο». Βάζεις τον γείτονα στην αρχή της ουράς αν η ακμή είναι 0, στο τέλος αν είναι 1. Η ουρά μένει ταξινομημένη κατά απόσταση, χωρίς σωρό. Εδώ όμως μια κορυφή μπορεί να βελτιωθεί αφού ανακαλυφθεί, γι' αυτό ο έλεγχος είναι dist[u] + w < dist[v] και όχι «δεν έχει επισκεφθεί».

Παγίδες

  • Σε πλέγμα, οι κορυφές είναι κελιά. Μην φτιάχνεις λίστα γειτνίασης: κράτα τα τέσσερα dr, dc και έλεγξε τα όρια.
  • Για διμερότητα (Building Teams) τρέχεις BFS από κάθε κορυφή που δεν έχει χρώμα. Ο γράφος μπορεί να μην είναι συνεκτικός.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/bfs.cpp
// Breadth-first search on an unweighted graph: shortest distances in edges from src.
// dist[v] = -1 if v is unreachable. O(n + m).
// Plus 0-1 BFS: edge weights 0 or 1, a deque instead of Dijkstra's heap. O(n + m).

vector<int> bfs(const vector<vector<int>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// adj[u] = list of (v, w) with w in {0, 1}. Unreachable: LLONG_MAX.
vector<ll> zeroOneBfs(const vector<vector<pair<int, int>>>& adj, int src) {
    int n = adj.size();
    vector<ll> dist(n, LLONG_MAX);
    deque<int> dq;
    dist[src] = 0;
    dq.push_back(src);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) {
                    dq.push_front(v);
                } else {
                    dq.push_back(v);
                }
            }
        }
    }
    return dist;
}

Ελέγχθηκε σε 1.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.