結果

問題 No.556 仁義なきサルたち
ユーザー algon_320
提出日時 2017-08-11 23:06:37
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 19 ms
コード長 2,449 Byte
コンパイル時間 1,592 ms
使用メモリ 1,620 KB
最終ジャッジ日時 2019-12-29 01:07:14

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
test1.txt AC 3 ms
1,528 KB
test2.txt AC 3 ms
1,532 KB
test3.txt AC 4 ms
1,528 KB
test4.txt AC 3 ms
1,532 KB
test5.txt AC 4 ms
1,532 KB
test6.txt AC 3 ms
1,536 KB
test7.txt AC 3 ms
1,536 KB
test8.txt AC 4 ms
1,540 KB
test9.txt AC 5 ms
1,536 KB
test10.txt AC 5 ms
1,540 KB
test11.txt AC 5 ms
1,544 KB
test12.txt AC 5 ms
1,544 KB
test13.txt AC 6 ms
1,540 KB
test14.txt AC 11 ms
1,576 KB
test15.txt AC 11 ms
1,580 KB
test16.txt AC 11 ms
1,576 KB
test17.txt AC 17 ms
1,620 KB
test18.txt AC 18 ms
1,616 KB
test19.txt AC 19 ms
1,620 KB
x_append10.txt AC 18 ms
1,616 KB
x_append11.txt AC 18 ms
1,620 KB
x_append12.txt AC 19 ms
1,620 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define REPW(i,n) for(i=0;i<(int)(n);++i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : " "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> *i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> " " >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

struct union_find {
    vector<int> data;
    union_find(int size) : data(size, -1) { }
    void unite(int x, int y) {
        x=root(x);
        y=root(y);
        if(x>y) swap(x,y);
        if(x==y) return;
        if(size(x)<size(y)) swap(x,y);
        data[x]+=data[y];
        data[y]=x;
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
signed main() {
    int n,m;
    cin>>n>>m;
    union_find uf(n);
    REP(i,m) {
        int a,b;
        cin>>a>>b;
        uf.unite(a-1,b-1);
    }
    REP(i,n) {
        cout<<uf.root(i)+1<<endl;
    }
    return 0;
}
0