結果
問題 | No.1640 簡単な色塗り |
ユーザー |
|
提出日時 | 2021-08-06 22:10:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 1,079 bytes |
コンパイル時間 | 999 ms |
コンパイル使用メモリ | 85,680 KB |
実行使用メモリ | 19,724 KB |
最終ジャッジ日時 | 2024-06-29 15:14:09 |
合計ジャッジ時間 | 14,377 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
コンパイルメッセージ
main.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 18 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<atcoder/dsu>using namespace std;int N;void dfs(int u,int p,vector<int>&ans,vector<vector<pair<int,int> > >&G){for(pair<int,int>e:G[u]){int v=e.first;if(v!=p){ans[e.second]=v;dfs(v,u,ans,G);}}}main(){cin>>N;vector<int>A(N),B(N);atcoder::dsu P(N);for(int i=0;i<N;i++){cin>>A[i]>>B[i];A[i]--,B[i]--;P.merge(A[i],B[i]);}vector<vector<int> >E(N);for(int i=0;i<N;i++){int p=P.leader(A[i]);E[p].push_back(i);}atcoder::dsu Q(N);vector<int>ans(N);vector<vector<pair<int,int> > >G(N);for(int i=0;i<N;i++)if(i==P.leader(i)){int fi=-1;for(int ei:E[i]){int a=A[ei],b=B[ei];if(Q.same(a,b)){if(fi!=-1){cout<<"No"<<endl;return 0;}fi=ei;}else{G[a].push_back(make_pair(b,ei));G[b].push_back(make_pair(a,ei));Q.merge(a,b);}}if(fi==-1){cout<<"No"<<endl;return 0;}dfs(A[fi],-1,ans,G);ans[fi]=A[fi];}cout<<"Yes"<<endl;for(int i=0;i<N;i++)cout<<ans[i]+1<<endl;}