This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C" #include <bits/stdc++.h> using namespace std; #include "../bfs.h" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; Graph g(n); REP(i,n) { int u, k; cin >> u >> k; --u; while (k--) { int v; cin >> v; --v; g.add_edge(u, v); } } auto dist = g.bfs(0); REP(i,n) { cout << (i+1) << ' ' << dist[i] << '\n'; } return 0; }
#line 1 "Graph/tests/aizu_alds1_11_c_bfs.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C" #include <bits/stdc++.h> using namespace std; #line 1 "Graph/bfs.h" // BFS {{{ // - Index from 0 // - Directed // - Supports multi-source BFS // - Supports reconstruct path // // Tested: // - https://oj.vnoi.info/problem/vmunch // - https://oj.vnoi.info/problem/vcoldwat // - (trace) https://cses.fi/problemset/task/1667/ // - (multi-source) https://cses.fi/problemset/task/1193/ struct Graph { Graph(int _n) : n(_n), g(n) {} void add_edge(int u, int v, bool bi_directional = false) { g[u].push_back(v); if (bi_directional) g[v].push_back(u); } // return // - shortest distance from start -> target // - path // If no path -> returns -1 pair<int, vector<int>> bfs(int start, int target) const { assert(0 <= start && start < n); assert(0 <= target && target < n); auto [dist, trace] = _bfs({start}, target); if (dist[target] < 0) { return {dist[target], {}}; } vector<int> path; for (int u = target; u != start; u = trace[u]) { path.push_back(u); } path.push_back(start); reverse(path.begin(), path.end()); return {dist[target], path}; } // return: dist: vector<int>, dist[u] = shortest distance from start -> u vector<int> bfs(int start) const { assert(0 <= start && start < n); return _bfs({start}, -1).first; } // multi-source BFS // Return: dist[u] = shortest distance from any source -> u vector<int> bfs(vector<int> starts) const { return _bfs(starts, -1).first; } // private: // Start BFS from start, and stop when reaching target. // Target = -1 -> BFS whole graph // Returns {distance, trace} pair<vector<int>, vector<int>> _bfs(vector<int> starts, int target) const { assert(-1 <= target && target < n); queue<int> qu; vector<int> dist(g.size(), -1); vector<int> trace(g.size(), -1); for (int start : starts) { assert(0 <= start && start < n); dist[start] = 0; qu.push(start); } while (!qu.empty()) { auto u = qu.front(); qu.pop(); if (u == target) { break; } for (const auto& v : g[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; trace[v] = u; qu.push(v); } } } return {dist, trace}; } int n; vector<vector<int>> g; }; // }}} #line 7 "Graph/tests/aizu_alds1_11_c_bfs.test.cpp" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; Graph g(n); REP(i,n) { int u, k; cin >> u >> k; --u; while (k--) { int v; cin >> v; --v; g.add_edge(u, v); } } auto dist = g.bfs(0); REP(i,n) { cout << (i+1) << ' ' << dist[i] << '\n'; } return 0; }