結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-11 22:40:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,370 bytes |
コンパイル時間 | 1,430 ms |
コンパイル使用メモリ | 121,700 KB |
最終ジャッジ日時 | 2025-01-05 02:12:26 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include<string> #include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<array> #include<map> using namespace std; typedef long long int llint; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase const int mod=1000000007; const int big=1e9+10; const long double pai=3.141592653589793238462643383279502884197; const long double eps=1e-9; template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}} template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}} int gcd(int a,int b){if(a%b==0){return b;}else return gcd(b,a%b);} int main(void){ int n,m,i,j,a,b;cin>>n>>m; vector<int>boss(n);//自分のうえ vector<int>num(n); for(i=0;i<n;i++){boss[i]=i;num[i]=1;} for(i=0;i<m;i++){ cin>>a>>b;a--;b--; while(boss[a]!=a){a=boss[a];} while(boss[b]!=b){b=boss[b];} if(a==b){continue;} if(num[a]<num[b]){swap(a,b);} else if(num[a]==num[b]&&a>b){swap(a,b);} //aがかつ num[a]+=num[b]; boss[b]=a; } for(i=0;i<n;i++){ a=i; while(boss[a]!=a){a=boss[a];} cout<<a+1<<endl; } return 0; }