結果
問題 | No.1553 Lovely City |
ユーザー |
|
提出日時 | 2021-06-18 23:45:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 406 ms / 2,000 ms |
コード長 | 3,896 bytes |
コンパイル時間 | 1,257 ms |
コンパイル使用メモリ | 115,072 KB |
実行使用メモリ | 45,820 KB |
最終ジャッジ日時 | 2024-06-22 21:36:49 |
合計ジャッジ時間 | 12,043 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:145:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 145 | for(auto [a, b]: ans) cout << a+1 << ' ' << b+1 << endl; | ^
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;class Scc{public:int N;vector<vector<int>> G;vector<vector<int>> G_inv;vector<int> idx;Scc(int n){N = n;G = vector<vector<int>>(n, vector<int>());G_inv = vector<vector<int>>(n, vector<int>());used = vector<bool>(n, false);idx = vector<int>(n);}void add_edge(int from, int to){G[from].push_back(to);G_inv[to].push_back(from);}vector<vector<int>> scc(){vector<vector<int>> ans;for(int i = 0; i < N; i++){if(!used[i]) dfs1(i);}clear();int cur = 0;for(int i = vs.size()-1; i >= 0; i--){if(!used[vs[i]]) {dfs2(vs[i], cur);cur++;ans.push_back(buf);buf.clear();}}return ans;}private:vector<bool> used;vector<int> vs;vector<int> buf;void clear(){for(int i = 0; i < N; i++) used[i] = false;}void dfs1(int v){used[v] = true;for(int i = 0; i < G[v].size(); i++){if(!used[G[v][i]]) dfs1(G[v][i]);}vs.push_back(v);}void dfs2(int v, int k){used[v] = true;idx[v] = k;for(int i = 0; i < G_inv[v].size(); i++){if(!used[G_inv[v][i]]) dfs2(G_inv[v][i], k);}buf.push_back(v);}};struct UnionFind {vector<int> data;UnionFind(int size) : data(size, -1) {}bool unionSet(int x, int y) {x = root(x); y = root(y);if (x != y) {if (data[y] < data[x]) swap(x, y);data[x] += data[y]; data[y] = x;}return x != y;}bool findSet(int x, int y) {return root(x) == root(y);}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}};using P = pair<int, int>;int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int n, m; cin >> n >> m;vector<int> u(m), v(m);Scc scc(n);UnionFind uf(n);for(int i = 0; i < m; i++){cin >> u[i] >> v[i]; u[i]--; v[i]--;scc.add_edge(u[i], v[i]);uf.unionSet(u[i], v[i]);}auto v_scc = scc.scc();vector<bool> dag(n, true);vector<vector<int>> components(n);for(auto u: v_scc){if(u.size() > 1) dag[uf.root(u[0])] = false;for(int x : u){components[uf.root(x)].push_back(x);}}vector<P> ans;for(int i = 0; i < n; i++){if(components[i].size() <= 1) continue;int sz = components[i].size();for(int j = 0; j < sz-1; j++){ans.push_back(P(components[i][j], components[i][j+1]));}if(!dag[i]){ans.push_back(P(components[i][sz-1], components[i][0]));}}cout << ans.size() << endl;for(auto [a, b]: ans) cout << a+1 << ' ' << b+1 << endl;}