結果
問題 | No.1553 Lovely City |
ユーザー |
|
提出日時 | 2021-06-18 21:58:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 620 ms / 2,000 ms |
コード長 | 2,354 bytes |
コンパイル時間 | 1,144 ms |
コンパイル使用メモリ | 89,296 KB |
実行使用メモリ | 61,176 KB |
最終ジャッジ日時 | 2024-06-22 20:20:41 |
合計ジャッジ時間 | 15,825 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
コンパイルメッセージ
a.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
ソースコード
#line 1 "a.cpp"#include<iostream>#include<algorithm>using namespace std;#line 1 "/home/kotatsugame/library/graph/SCC.cpp"//Strongly Connected Components#include<vector>struct SCC{int n;vector<int>comp,order;vector<bool>used;vector<vector<int> >G,RG;SCC(int _n=0):n(_n),comp(_n,-1),used(_n,false),G(_n),RG(_n){}void add_edge(int from,int to){G[from].push_back(to);RG[to].push_back(from);}void copy(const vector<vector<int> >&H){for(int i=0;i<H.size();i++){for(int j=0;j<H[i].size();j++){G[i].push_back(H[i][j]);RG[H[i][j]].push_back(i);}}}int operator[](int u)const{return comp[u];}void dfs(int u){used[u]=true;for(int i=0;i<G[u].size();i++)if(!used[G[u][i]])dfs(G[u][i]);order.push_back(u);}void rdfs(int u,int cnt){comp[u]=cnt;for(int i=0;i<RG[u].size();i++)if(comp[RG[u][i]]==-1)rdfs(RG[u][i],cnt);}int build(){for(int i=0;i<n;i++)if(!used[i])dfs(i);int cnt=0;for(int i=n-1;i>=0;i--)if(comp[order[i]]==-1)rdfs(order[i],cnt++);return cnt;}int build(vector<vector<int> >&H){int ret=build();H.assign(ret,vector<int>());for(int i=0;i<n;i++){for(int j=0;j<G[i].size();j++){if(comp[i]!=comp[G[i][j]])H[comp[i]].push_back(comp[G[i][j]]);}}return ret;}};#line 5 "a.cpp"int N,M;vector<pair<int,int> >E;bool vis[2<<17];vector<int>G[2<<17];vector<int>vs[2<<17];vector<int>now;void dfs(int u){vis[u]=true;now.push_back(u);for(int v:G[u])if(!vis[v]){dfs(v);}}main(){cin>>N>>M;SCC P(N);for(int i=0;i<M;i++){int u,v;cin>>u>>v;u--,v--;P.add_edge(u,v);}vector<vector<int> >H;int K=P.build(H);for(int i=0;i<N;i++)vs[P[i]].push_back(i);for(int i=0;i<K;i++)for(int v:H[i]){G[i].push_back(v);G[v].push_back(i);}for(int i=0;i<K;i++)if(!vis[i]){now.clear();dfs(i);sort(now.begin(),now.end());int cnt=0;for(int u:now)if(vs[u].size()>=2)cnt++;if(cnt==0){for(int j=0;j<now.size()-1;j++){E.push_back(make_pair(vs[now[j]][0],vs[now[j+1]][0]));}}else{vector<int>vvs;for(int u:now)for(int v:vs[u])vvs.push_back(v);int f=vvs.back();for(int u:vvs){E.push_back(make_pair(f,u));f=u;}}}cout<<E.size()<<endl;for(pair<int,int>p:E)cout<<p.first+1<<" "<<p.second+1<<endl;}