UVA11987:并查集支持删除操作的实现与应用

Almost Union-Find

 UVA - 11987 

这题的重点在于一些点会被删除&＃xff0c;但是我们知道&＃xff0c;如果不是根节点的还好&＃xff0c;一旦删除根节点&＃xff0c;该并查集的结构就被严重破坏了&＃xff0c;因此我们选择设置一个虚点&＃xff0c;他不存在&＃xff0c;也不贡献点的数量&＃xff0c;也不贡献值&＃xff0c;仅仅是存在于那里为我们来维持结构。

为了达到这个目的&＃xff0c;我们为每个点设定一个id值每当这个点经历了一次删除操作&＃xff0c;我们就为他更换一个新的ip。再检索时就用这个新的ID进行检索&＃xff0c;而旧的ID就放在那里储存和维持原来的结构。特别需要注意的是&＃xff0c;我们总是通过点来确定&＃xff0c;我们到底是要搜索哪个id而在后续的搜索和合并都使用id值来进行合并。即信息的储存仅与id有关&＃xff0c;而id与点有关&＃xff0c;但点与信息无关。

具体细节见代码&＃xff1a;

#include
#include
#define int long long
using namespace std;
const int size&＃61;1e6&＃43;5;
int tot;
int fa[size],id[size],cnt[size],sum[size];
void init(int n)
{tot&＃61;n&＃43;1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){cnt[i]&＃61;1;sum[i]&＃61;i;fa[i]&＃61;i;id[i]&＃61;i;}
}
int find(int x)
{return x&＃61;&＃61;fa[x]?x:fa[x]&＃61;find(fa[x]);
}
void merge(int x,int y)
{int fx&＃61;find(id[x]),fy&＃61;find(id[y]);if(fx&＃61;&＃61;fy) return;cnt[fy]&＃43;&＃61;cnt[fx];sum[fy]&＃43;&＃61;sum[fx];cnt[fx]&＃61;0,sum[fx]&＃61;0;fa[fx]&＃61;fy;
}
void move(int x,int y)
{int fx&＃61;find(id[x]),fy&＃61;find(id[y]);id[x]&＃61;&＃43;&＃43;tot;fa[tot]&＃61;fy;sum[fy]&＃43;&＃61;x;cnt[fy]&＃43;&＃43;;sum[fx]-&＃61;x;cnt[fx]--;
}
int32_t main()
{int n,k;while(~scanf("%lld%lld",&n,&k)){init(n);while(k--){int op;scanf("%lld",&op);if(op&＃61;&＃61;1){int a,b;scanf("%lld%lld",&a,&b);merge(a,b);}if(op&＃61;&＃61;2){int a,b;scanf("%lld%lld",&a,&b);move(a,b);}if(op&＃61;&＃61;3){int x;scanf("%lld",&x);int fx&＃61;find(id[x]);cout<}