#195665 (C++11) No.556 仁義なきサルたち

• 問題: No.556 仁義なきサルたち
• ユーザー: beet
• 提出日時: 2017-08-11 22:38:18
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 19 ms / 2,000 ms
• コード長: 774 bytes
• コンパイル時間: 1,216 ms
• コンパイル使用メモリ: 149,228 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-08-02 23:04:08
• 合計ジャッジ時間: 2,218 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	2 ms; 4,380 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,376 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	3 ms; 4,380 KB
testcase_10	AC	3 ms; 4,380 KB
testcase_11	AC	3 ms; 4,376 KB
testcase_12	AC	3 ms; 4,384 KB
testcase_13	AC	8 ms; 4,380 KB
testcase_14	AC	9 ms; 4,380 KB
testcase_15	AC	10 ms; 4,376 KB
testcase_16	AC	15 ms; 4,380 KB
testcase_17	AC	16 ms; 4,376 KB
testcase_18	AC	17 ms; 4,380 KB
testcase_19	AC	17 ms; 4,380 KB
testcase_20	AC	19 ms; 4,376 KB
testcase_21	AC	19 ms; 4,376 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct UnionFind{
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int size){init(size);}
  void init(int size){
    r.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) r[i]=1,p[i]=i;
  }
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    if(r[x]==r[y]&&x>y) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};

signed main(){
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    uf.unite(a,b);
  }
  for(int i=0;i<n;i++) cout<<uf.find(i)+1<<endl;
  return 0;
}