結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-18 22:36:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 2,931 bytes |
コンパイル時間 | 1,481 ms |
コンパイル使用メモリ | 119,860 KB |
最終ジャッジ日時 | 2025-01-22 09:31:51 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <algorithm>#include <cmath>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>#define mkp make_pair#define mkt make_tuple#define rep(i, n) for (int i = 0; i < (n); ++i)#define all(v) v.begin(), v.end()using namespace std;typedef long long ll;const ll MOD = 1e9 + 7;// const ll MOD = 998244353;template <class T>void chmin(T &a, const T &b) {if (a > b) a = b;}template <class T>void chmax(T &a, const T &b) {if (a < b) a = b;}class DisjointSet {public:int N;vector<int> rank, p;vector<int> sz;DisjointSet() {}DisjointSet(int n) : N(n), rank(n), p(n), sz(n) {for (int i = 0; i < N; i++) makeSet(i);}void makeSet(int x) {p[x] = x;rank[x] = 0;sz[x] = 1;}bool same(int x, int y) {return leader(x) == leader(y);}void unite(int x, int y) {if (same(x, y)) return;link(leader(x), leader(y));}void link(int x, int y) {if (rank[x] > rank[y]) swap(x, y);p[x] = y;sz[y] += sz[x];if (rank[x] == rank[y]) {++rank[y];}}int leader(int x) {if (x != p[x]) p[x] = leader(p[x]);return p[x];}int size(int x) {return sz[leader(x)];}};void solve() {int N, M;cin >> N >> M;vector<int> U(M), V(M);rep(i, M) cin >> U[i] >> V[i];rep(i, M) {U[i]--;V[i]--;}vector<vector<int>> g(N);rep(i, M) g[U[i]].push_back(V[i]);DisjointSet us(N);rep(i, M) us.unite(U[i], V[i]);vector<vector<int>> nodes(N);rep(i, N) nodes[us.leader(i)].push_back(i);vector<vector<int>> e_idxs(N);rep(i, M) e_idxs[us.leader(U[i])].push_back(i);vector<int> in(N, 0);vector<pair<int, int>> output;for (int k = 0; k < N; k++) {if (nodes[k].empty()) continue;for (auto ed : e_idxs[k]) in[V[ed]]++;queue<int> Q;for (auto id : nodes[k])if (in[id] == 0) Q.push(id);vector<int> order;while (!Q.empty()) {auto now = Q.front();Q.pop();order.push_back(now);for (auto nex : g[now]) {in[nex]--;if (in[nex] == 0) Q.push(nex);}}if (order.size() == nodes[k].size()) {for (int i = 0; i + 1 < order.size(); i++) output.emplace_back(order[i], order[i + 1]);} else {rep(i, nodes[k].size())output.emplace_back(nodes[k][i], nodes[k][(i + 1) % (int)nodes[k].size()]);}}cout << output.size() << "\n";for (auto [a, b] : output) cout << a + 1 << " " << b + 1 << "\n";}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}