白準アルゴリズム18116号:ロボット組立

リンク

https://www.acmicpc.net/problem/18116

質問する

聖圭はロボットを組み立てる必要がある.箱の中にはロボットの部品がたくさん混ざっている.しかし、どの部品がどのロボットの部品なのかは表示されません.号材は電子科で、2つの部品を見ると同じロボットの部品であることがわかります.だから聖圭は浩在の指示に従って部品を整理することにした.
部品は1～106の整数で表されます.また、部品iが属するロボットもロボット(i)と表示される.例えば、部品11および部品22がロボットAの部品であることが知られている場合、robot(11)はロボットA、robot(22)もロボットAを表す.
異なるロボットには汎用部品がありません.すなわち、ある部品がロボットAの部品であれば、ロボットBの部品であってはならない.
胡才には2つの指示がある.

は、2つの異なる部品、2つの部品が同じロボットの部品であることを教えてくれます.

部品iについて、これまでに知っていたロボット(i)の部品がいくつあるかを尋ねる.
初期には部品に関する情報は存在しませんでした.

入力

1行目に号材の指示回数Nがある.(1 ≤ N ≤ 106)
次の行からN個の指示があります.
2つの部品が同じロボットの部品であることが知られると、(I)υa bの形で入る.部品aと部品bは、同じロボットの部品であるという意味です.(1≦a,b≦106,a≠b,a,bは整数)
あるロボットに何個の部品があるかと聞かれると、Qcの形で入ります.これは、これまでに知っていたロボット(c)の部品がいくつあるかを意味します.(1≦c≦106、cは整数)
入力は少なくとも1回qcの形態に入る.

しゅつりょく

Qで始まる入力については、行ごとに1つずつ出力され、これまで知られていたこのロボットの部品数です.

入力と出力の例

プールコード（C++）

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;

struct UnionFind {
	vector<int> parent, rank, cnt;
	UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1) {
		iota(parent.begin(), parent.end(), 0);
	}
	int Find(int x) {
		return x == parent[x] ? x : parent[x] = Find(parent[x]);
	}
	bool Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return 0;
		if (rank[a] < rank[b]) swap(a, b);
		parent[b] = a;
		rank[a] += rank[a] == rank[b];
		cnt[a] += cnt[b];
		return 1;
	}
};

int main() {
  fastio;
  int N; cin >> N;
  UnionFind UF(1000001);
  while(N--){
    char c; cin >> c;
    if(c == 'I'){
      int a,b; cin >> a >> b;
      UF.Union(a, b);
    }
    else{ // Q
      int c; cin >> c;
      cout << UF.cnt[UF.Find(c)] << "\n";
    }
  }
  return 0;
}

問題では,異なるロボットは共通部品を持たず,これまでに何個の部品が発見されたかを尋ねることでdisconnection-set集合の大きさを求めることができる.
nとaとbの最大値は100000万であるため、Union Findの初期設定を行う場合は、アレイエラーを回避するために100001に設定する必要があります.