HDU--2473 junk mail （并查集，函数）

Love The Way You Lie 2022-08-10 13:49 7阅读 0赞

一见到这一题时，顿时就犯二了。就去手动实现并查集关系的替换，可是结果你懂得......

这一题和普通并查集的区别仅在于他有删除操作，但是并查集里，节点是相互有联系的，删除节点很可能使数据间的关系发生改变，怎么办呢？

还记得从初中都是学的 function 吗？

既然我不能随便删除节点，那就让他保留下来吧。不过我要改变映射关系

<table> 
 <tbody> 
  <tr> 
   <td>X</td> 
   <td>function</td> 
   <td>Y</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>&nbsp;</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>&nbsp;</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>&nbsp;</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>&nbsp;</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>&nbsp;</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>&nbsp;</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>&nbsp;</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>&nbsp;</td> 
   <td>8</td> 
  </tr> 
  <tr> 
   <td>......</td> 
   <td>&nbsp;</td> 
   <td>.....</td> 
  </tr> 
 </tbody> 
</table>

开始时，每个x对应于原值，如果要删除x =1，则将f（x）更新我选的是N，再删除就更新为N+1........这只是为了便于赋值，和节省空间。题目中的数据是不包括N的。

那么最后怎么统计集合个数呢？当然是find（fun(x) )了，因为此时的fun【x】才是x的真实值，其母节点也代表x在位置。

#include <cstdio>
    #include <cstring>
    const int N=1100000;//最坏情况是删除了一百万次，加原来的十万次
    int pa[N],fun[N],flag[N];
    
    int find(int x)
    {
    	if(x!=pa[x])
    	{
    		pa[x]=find(pa[x]);
    	}
    	return pa[x];
    }
    
    void merge(int x,int y)
    {
    	int px=find(x),py=find(y);
    	if(px!=py)
    	pa[px]=py; 
    } 
    void initial(int n)
    {
    	for(int i=0;i<n;i++)
    	{
    		pa[i]=i;fun[i]=i;
    	}
    }
    int main()
    {
    	int n,m,scaler=1;
    	while(scanf("%d%d",&n,&m)==2)
    	{
    		if(m==0&&n==0)break;
    		initial(n);
    		char s[5];int x,y,top=n;
    		while(m--)
    		{
    		scanf("%s",s);
    		if(s[0]=='M')
    		{
    			scanf("%d%d",&x,&y);
    			merge(fun[x],fun[y]);
    		}
    		else if(s[0]=='S')
    		{
    			scanf("%d",&x);
    			fun[x]=top;
    			pa[top]=top;
    			++top;
    		}
    		}
    		memset(flag,0,sizeof(flag));
    		int count=0;
    		for(int i=0;i<n;i++)
    		{
    			if(flag[find(fun[i])]==0)
    			{
    				flag[find(fun[i])]=1;
    				count++;
    			}
    		}
    		printf("Case #%d: %d\n",scaler++,count);
    	}
    }