結果
問題 | No.1553 Lovely City |
ユーザー |
👑 ![]() |
提出日時 | 2021-06-18 21:56:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 361 ms / 2,000 ms |
コード長 | 4,488 bytes |
コンパイル時間 | 3,233 ms |
コンパイル使用メモリ | 225,704 KB |
最終ジャッジ日時 | 2025-01-22 09:14:51 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 1000000007;// constexpr int MOD = 998244353;constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;struct StronglyConnectedComponents {std::vector<int> id;std::vector<std::vector<int>> vertices, comp;StronglyConnectedComponents(const std::vector<std::vector<int>> &graph, bool heavy = false) : graph(graph), heavy(heavy) {n = graph.size();rev_graph.resize(n);for (int i = 0; i < n; ++i) for (int e : graph[i]) rev_graph[e].emplace_back(i);used.assign(n, false);id.assign(n, -1);for (int i = 0; i < n; ++i) {if (!used[i]) dfs(i);}int now = 0;for (int i = n - 1; i >= 0; --i) {if (id[order[i]] == -1) {if (heavy) vertices.emplace_back();rev_dfs(order[i], now++);}}comp.resize(now);for (int i = 0; i < n; ++i) for (int e : graph[i]) {if (id[i] != id[e]) comp[id[i]].emplace_back(id[e]);}// if (heavy) {// for (int i = 0; i < now; ++i) std::sort(vertices[i].begin(), vertices[i].end());// }}private:bool heavy;int n;std::vector<std::vector<int>> graph, rev_graph;std::vector<bool> used;std::vector<int> order;void dfs(int ver) {used[ver] = true;for (int e : graph[ver]) {if (!used[e]) dfs(e);}order.emplace_back(ver);}void rev_dfs(int ver, int now) {id[ver] = now;if (heavy) vertices[now].emplace_back(ver);for (int e : rev_graph[ver]) {if (id[e] == -1) rev_dfs(e, now);}}};struct UnionFind {UnionFind(int n) : data(n, -1) {}int root(int ver) { return data[ver] < 0 ? ver : data[ver] = root(data[ver]); }bool unite(int u, int v) {u = root(u);v = root(v);if (u == v) return false;if (data[u] > data[v]) std::swap(u, v);data[u] += data[v];data[v] = u;return true;}bool same(int u, int v) { return root(u) == root(v); }int size(int ver) { return -data[root(ver)]; }private:std::vector<int> data;};std::vector<int> topological_sort(const std::vector<std::vector<int>> &graph) {int n = graph.size();std::vector<int> deg(n, 0);for (int i = 0; i < n; ++i) {for (int e : graph[i]) ++deg[e];}std::queue<int> que;for (int i = 0; i < n; ++i) {if (deg[i] == 0) que.emplace(i);}std::vector<int> res;while (!que.empty()) {int ver = que.front(); que.pop();res.emplace_back(ver);for (int e : graph[ver]) {if (--deg[e] == 0) que.emplace(e);}}return res.size() == n ? res : std::vector<int>();}int main() {int n, m; cin >> n >> m;vector<vector<int>> graph(n);while (m--) {int u, v; cin >> u >> v; --u; --v;graph[u].emplace_back(v);}StronglyConnectedComponents scc(graph, true);const int x = scc.comp.size();UnionFind uf(x);REP(i, x) for (int e : scc.comp[i]) uf.unite(i, e);map<int, vector<int>> root;REP(i, x) root[uf.root(i)].emplace_back(i);vector<int> ts = topological_sort(scc.comp);assert(!ts.empty());vector<int> inv(x, -1);REP(i, x) inv[ts[i]] = i;vector<int> a, b;for (auto [_, v] : root) {sort(ALL(v), [&](int l, int r) -> bool { return inv[l] < inv[r]; });int last = -1;bool need_loop = false;for (int e : v) {for (int ver : scc.vertices[e]) {if (last != -1) {a.emplace_back(last);b.emplace_back(ver);}last = ver;}need_loop |= scc.vertices[e].size() > 1;}if (need_loop) {a.emplace_back(last);b.emplace_back(scc.vertices[v.front()].front());}}int k = a.size();cout << k << '\n';REP(i, k) cout << a[i] + 1 << ' ' << b[i] + 1 << '\n';return 0;}