結果

問題 No.556 仁義なきサルたち
ユーザー alpha_virginisalpha_virginis
提出日時 2017-08-11 23:19:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,801 bytes
コンパイル時間 1,683 ms
コンパイル使用メモリ 172,032 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 21:54:24
合計ジャッジ時間 2,550 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;
const long mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct N001 {
   long n;
   std::vector<long> parents;
   std::vector<long> numbers;
   N001(long n_) : n(n_), parents(n+1, -1), numbers(n+1, 1) {
   }
};
long find(N001& s, long x) {
   if( s.parents[x] == -1 ) return x;
   return s.parents[x] = find(s, s.parents[x]);
}
bool same(N001& s, long x, long y) {
   return find(s, x) == find(s, y);
}
void unite(N001& s, long x, long y) {
   long x2 = find(s, x);
   long y2 = find(s, y);
   if( x2 == y2 ) return;
   // if( not ( x2 <= y2 ) )
   //    std::swap(x2, y2);
   // if( not ( s.numbers[x2] <= s.numbers[y2] ) )
   //    std::swap(x2, y2);
   s.parents[x2] = y2;
   s.numbers[y2] += s.numbers[x2];
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      long n, m; scan(n, m);
      N001 uf(n);
      for(long i = 0; i < m; ++i) {
         long a, b; scan(a, b);
         long a2 = find(uf, a);
         long b2 = find(uf, b);
         if( uf.numbers[a2] != uf.numbers[b2] ) {
            if( uf.numbers[a2] < uf.numbers[b2] ) {
               unite(uf, a2, b2);
            }
            else {
               unite(uf, b2, a2);
            }
         }
         else {
            if( a2 < b2 ) {
               unite(uf, b2, a2);
            }
            else {
               unite(uf, a2, b2);
            }
         }
      }
      for(long i = 1; i <= n; ++i) {
         printf("%ld\n", find(uf, i));
      }
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}
0