描述
题解
并查集+设立虚父节点(马甲),第一眼看,是不是很懵逼?马甲?what’s this?
第一次做这种并查集,看了题解(源码)后,顿悟,pre[]
不再是够n
就行了,而需要留出拓展的空间,通过对虚父节点的操作来不断扩展并查集,就像给他套了一层马甲一般,而这个马甲pre_[]
修饰(储存)了并查集的拓展信息,有趣~~~
这道题合并操作十分简单,在独立操作时,如果直接将原点独立,将会带来很多问题,毕竟并查集里环环相扣,所以可以另外建立一个虚结点来替代他加到并查集中,这个替代的信息就存储在虚父节点pre_[]
中,也就是马甲中。
对这个马甲的解释只是辅助我个人的理解,可能解释不太严谨,但是的确帮助我理解了。
代码
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m;
int pre[10 * MAXN];
int pre_[MAXN];
set<int> st;
void init()
{
for (int i = 0; i < n; i++)
{
pre[i] = i;
pre_[i] = i;
}
}
int find(int x)
{
if (x == pre[x])
{
return pre[x];
}
pre[x] = find(pre[x]);
return pre[x];
}
void join(int x, int y)
{
int a = find(x);
int b = find(y);
if (a == b)
{
return ;
}
pre[a] = b;
}
int main()
{
int cas = 0, a, b;
char str[2];
while (scanf("%d %d", &n, &m) == 2 && (n + m))
{
init();
st.clear();
int num = n;
while (m--)
{
scanf("%s", str);
if (str[0] == 'S')
{
scanf("%d", &a);
pre_[a] = num++;
pre[pre_[a]] = pre_[a];
}
else
{
scanf("%d %d", &a, &b);
join(pre_[a], pre_[b]);
}
}
for (int i = 0; i < n; i++)
{
st.insert(find(pre_[i]));
}
printf("Case #%d: %lu\n", ++cas, st.size());
}
return 0;
}