HDU-2473 Junk-Mail Filter 并查集的删除

本文主要是介绍HDU-2473 Junk-Mail Filter 并查集的删除，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*解决方法: 为每一个结点加一个虚根,这样每个结点都是叶子结点.插入结点时,把它们都并到虚根的集合中.删除结点时,只要把它的父结点置为一个无用的虚根
*/#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
const int inf = 1<<30;
int n,m;
int p[maxn<<1];int find( int x )
{if( p[x] == x )return p[x];elsereturn p[x] = find(p[x]);
}
void merge( int a,int b )
{int x = find(a);int y = find(b);p[x] = y;
}void init()                                        //初始化   马甲
{for( int i = 0; i < n; i ++ )p[i] = i + n;for( int i = n; i <= n*2+m; i ++ )p[i] = i;
}
int main()
{char ch;int a,b,cas = 1;while( scanf("%d%d",&n,&m) != EOF , (n||m) ){init();int pos = n*2;for( int i = 0; i < m; i ++ ){getchar();ch = getchar();if( ch == 'M' ){scanf("%d%d",&a,&b);merge(a,b);}else if( ch == 'S' ){scanf("%d",&a);p[a] = pos++;}}int ans = 0;bool mark[maxn] = {0};for( int i = 0;i < n; i ++ )                //把出现过的集合标记{if( !mark[p[i] = find(p[i])]){mark[p[i]] = 1;ans++;}}printf("Case #%d: %d\n",cas++,ans);}return 0;
}

这篇关于HDU-2473 Junk-Mail Filter 并查集的删除的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---