并查集删点问题:
删点方法:造假点;
因为我们不知道要删除的点是根节点还是叶节点,所以如果直接删除(用其他点替换)可能会影响到其他节点,于是我们得到了做法:
全部修改,让构造的时候就没有使用真点,及一直用假点来代替,删点的时候只需更改原来的点指向的假点即可,即为造假点。
-
开两个数组,一个是原来的点,一个是用来标记点对应假点。
至于怎么判断有多少个集合:
扫一遍所有点,找到每一个点的祖宗,如果没有被找到,答案加一并标记,否则不做处理(即找有多少种祖宗)。
并查集代码:
1 inline void init(){ 2 for (int i = 1;i <= n;i++) fa[i]=id[i]=i; 3 } 4 inline int find (int x){ 5 if (fa[x]==x) return x; 6 else return fa[x]=find(fa[x]); 7 } 8 inline void update(int x,int y){ 9 int fx=find(x),fy=find(y); 10 fa[fx]=fy; 11 return; 12 }
是M就正常合并:
1 if (a=='M'){ 2 int x=read()+1,y=read()+1; 3 if (find(id[x])!=find(id[y])) 4 update(id[x],id[y]); 5 }
否则造假点:
1 else { 2 int x=read()+1; 3 id[x]=++cnt; 4 fa[id[x]]=id[x]; 5 }
完整代码:
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int n,m,cnt,num,fa[2000005],id[2000005]; 6 bool flag[2000005]; 7 char a; 8 inline void init(){ 9 for (int i = 1;i <= n;i++) fa[i]=id[i]=i; 10 } 11 inline int find (int x){ 12 if (fa[x]==x) return x; 13 else return fa[x]=find(fa[x]); 14 } 15 inline void update(int x,int y){ 16 int fx=find(x),fy=find(y); 17 fa[fx]=fy; 18 return; 19 } 20 int read() 21 { 22 int s = 0, f = 1; 23 char ch = getchar(); 24 while(!isdigit(ch)) { 25 if(ch == '-') f = -1; 26 ch = getchar(); 27 } 28 while(isdigit(ch)) { 29 s = s * 10 + ch - '0'; 30 ch = getchar(); 31 } 32 return s * f; 33 } 34 int main() 35 { 36 while(n=read(),m=read(),n|m) 37 { 38 cnt=n; 39 init(); 40 for (int i = 1;i <= m;i++){ 41 scanf ("\n%c",&a); 42 if (a=='M'){ 43 int x=read()+1,y=read()+1; 44 if (find(id[x])!=find(id[y])) 45 update(id[x],id[y]); 46 } 47 else { 48 int x=read()+1; 49 id[x]=++cnt; 50 fa[id[x]]=id[x]; 51 } 52 } 53 memset(flag,0,sizeof(flag)); 54 int ans=0; 55 for(int i=1;i<=n;i++) 56 { 57 int tmp=find(id[i]); 58 if(!flag[tmp])//统计答案 59 { 60 ans++; 61 flag[tmp]=1; 62 } 63 } 64 printf("Case #%d: %d\n",++num,ans); 65 } 66 return 0; 67 }