結果
問題 | No.556 仁義なきサルたち |
ユーザー |
![]() |
提出日時 | 2017-08-11 23:22:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 1,425 bytes |
コンパイル時間 | 935 ms |
コンパイル使用メモリ | 93,696 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 21:56:24 |
合計ジャッジ時間 | 1,914 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <algorithm>#include <cstdio>#include <iostream>#include <map>#include <cmath>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <vector>#include <stdlib.h>#include <stdio.h>#include <bitset>#include <cstring>using namespace std;#define FOR(I,A,B) for(int I = (A); I < (B); ++I)#define CLR(mat) memset(mat, 0, sizeof(mat))typedef long long ll;// union - find tree !!!!!!!!!!!!!!!!!!!!!!!!!vector<int> par; //oyavector<int> rnk; //ki no hu ka sa// n要素で初期化void init(int n){par.resize(n);rnk.resize(n);FOR(i, 0, n){par[i] = i;rnk[i] = 1;}}//木の根を求めるint find(int x){if(par[x] == x) return x;else return par[x] = find(par[x]);}//xとyの属する集合を併合void unite(int x, int y){x = find(x);y = find(y);if(x == y) return;if(rnk[x] > rnk[y]) {par[y] = x;rnk[x] += rnk[y];rnk[y] = 0;} else if(rnk[x] < rnk[y]) {par[x] = y;rnk[y] += rnk[x];rnk[x] = 0;} else {if(x < y) {par[y] = x;rnk[x] += rnk[y];rnk[y] = 0;} else {par[x] = y;rnk[y] += rnk[x];rnk[x] = 0;}}return;}int main(){int N, M;cin >> N >> M;init(N+1);FOR(i,0,M) {int a, b; cin >> a >> b;unite(a, b);}FOR(i,1,N+1) {cout << find(i) << endl;}return 0;}