[AtCoder] ABC 168 D – .. (Double Dots)
問題
方針
幅優先探索で迷路を解くような感じで考えます。始点 \( 1 \) から幅優先探索を行い、到達した部屋の道しるべは、直前に来た部屋となります。隣接リストを作成し、到達した部屋のフラグを管理することで探索を行います。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N, M; cin >> N >> M; int A[M], B[M]; vector<int> adj[N]; for (int i = 0; i < M; i++) { cin >> A[i] >> B[i]; A[i]--; B[i]--; adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } deque<int> q; q.push_back(0); int ans[N]{}; bool vis[N]{}; vis[0] = true; while (!q.empty()) { int v = q.front(); q.pop_front(); for (int i : adj[v]) { if (vis[i]) continue; ans[i] = v; q.push_back(i); vis[i] = true; } } cout << "Yes\n"; for (int i = 1; i < N; i++) { cout << ans[i] + 1<< "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません