結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-18 22:03:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 795 ms / 2,000 ms |
コード長 | 2,745 bytes |
コンパイル時間 | 4,246 ms |
コンパイル使用メモリ | 198,100 KB |
最終ジャッジ日時 | 2025-01-22 09:18:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;struct SCC{vector<vector<int>> g, gr;int n, k;vector<int> cmp, vs;vector<bool> used;void dfs(int x){used[x]=1;for(auto y:g[x]){if(!used[y]) dfs(y);}vs.push_back(x);}void rdfs(int v, int k){used[v]=1;cmp[v]=k;for(auto y:gr[v]){if(!used[y]) rdfs(y, k);}}SCC(const vector<vector<int>> &g):g(g), n(g.size()), cmp(n), used(n){gr.resize(n);for(int x=0; x<n; x++) for(auto y:g[x]) gr[y].push_back(x);for(int i=0; i<n; i++){if(!used[i]) dfs(i);}fill(used.begin(), used.end(), 0);k=0;for(int i=vs.size()-1; i>=0; i--){if(!used[vs[i]]) rdfs(vs[i], k++);}}};int main(){int n, m;cin>>n>>m;vector<vector<int>> g(n), g1(n);for(int i=0; i<m; i++){int u, v;cin>>u>>v;u--; v--;g[u].push_back(v);g1[u].push_back(v);g1[v].push_back(u);}SCC scc(g);vector<int> w;bool used[200020]={};auto dfs=[&](auto dfs, int x)->void{used[x]=1;w.push_back(x);for(auto y:g1[x]){if(used[y]) continue;dfs(dfs, y);}};vector<P> ans;for(int i=0; i<n; i++){if(used[i]) continue;w.clear();dfs(dfs, i);map<int, int> mp;for(auto x:w){mp[scc.cmp[x]]++;}bool myon=0;for(auto p:mp){if(p.second!=1){myon=1;}}if(myon){for(int j=0; j<(int)w.size()-1; j++){ans.push_back({w[j], w[j+1]});}ans.push_back({w.back(), w[0]});}else{sort(w.begin(), w.end(), [&](int x, int y){ return scc.cmp[x]<scc.cmp[y];});for(int j=0; j<(int)w.size()-1; j++){ans.push_back({w[j], w[j+1]});}}}cout<<ans.size()<<endl;for(auto p:ans){cout<<p.first+1<<" "<<p.second+1<<endl;}return 0;}