题意:30000列军队,每列初始有1个。编号从1~30000.每次操作有两种,将现在第i列所在的列合并到第j列所在列的末尾。 或者查询第i列举例第j列的距离。
思路:带权并查集。合并时将第i列头节点接到第j列头节点上。然后直接查询dist取绝对值相减就好。
总结:一开始没看清题,以为要把从i列从当前所在列中截取出来接到第j列所在列末尾,就多了一个i列队头减i列元素数量的情况。
class DisjointSet{
public:
DisjointSet(int sz): sz_(sz){
fa_.resize(sz_);
iota(fa_.begin(), fa_.end(), 0);
set_size_.assign(sz_, 1);
dist_.assign(sz_, 0);
}
int findSet(int x){
if (fa_[x] == x){
return x;
}
return updateDist(x), fa_[x];
}
bool isSameSet(int x, int y){
return findSet(x) == findSet(y);
}
void unionSet(int x, int y){
int px = findSet(x);
int py = findSet(y);
fa_[px] = py;
dist_[px] = set_size_[py];
set_size_[py] += set_size_[px];
}
int getDist(int x){
updateDist(x);
return dist_[x];
}
private:
int sz_;
vector<int> fa_;
vector<int> set_size_;
vector<int> dist_;
inline void updateDist(int x){
if (fa_[x] == x){
return;
}
int par = fa_[x];
fa_[x] = findSet(fa_[x]);
dist_[x] += dist_[par];
}
};
void solve(){
int q;
cin >> q;
DisjointSet dsu(300010);
while (q --){
char t;
cin >> t;
int i, j;
cin >> i >> j;
if (t == 'M'){
dsu.unionSet(i, j);
}
else{
if (dsu.isSameSet(i, j) == false){
cout << -1 << '\n';
}
else{
cout << abs(dsu.getDist(j) - dsu.getDist(i)) - 1 << '\n';
}
}
}
}
标签:sz,dist,int,return,fa,findSet,NOI2002,洛谷,P1196
From: https://www.cnblogs.com/yxcblogs/p/18113955