[24445] 알고리즘 수업 - 너비 우선 탐색 2

https://www.acmicpc.net/problem/24445

24445번: 알고리즘 수업 - 너비 우선 탐색 2

인접리스트를 역순으로 정렬해두고 실제로 bfs를 돌리면서 순서를 기록해두자

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, s, vst[100001];

queue<int> q;

vector<int> adj[100001];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> s;

    int i;

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        adj[A].push_back(B);

        adj[B].push_back(A);

    }

    for (i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end(), greater<>());

    vst[s] = 1;

    q.push(s);

    int cnt = 2;

    while (!q.empty()) {

        int cur = q.front();

        q.pop();

        for (int& nxt : adj[cur]) {

            if (vst[nxt] == 0) {

                vst[nxt] = cnt++;

                q.push(nxt);

            }

        }

    }

    for (i = 1; i <= n; i++) cout << vst[i] << '\n';

    return 0;

}

---