pku3908 并查集的一点小变通

题目大意这样,给出一些节点,给出3种命令:
1、将a,b联通
2、查询a,b的联通状况
3、删除链接a的边。(如果之前a,c通过b联通,那么删除b的联通关系后a,c仍然认为联通)
1,2两种操作乍一看MS是并查集,但是第三种状况让人很恼火,尤其是想用路径压缩技巧的时候。那么,我们不妨转换下思路,删除a的联通关系可以认为将a节点重标号,把之前那个a节点认为是虚拟节点,这样联通性啥的都好保证了。详细请看代码:

Source Code

Problem: 3908User: yzhw
Memory: 1096KTime: 47MS
Language: G++Result: Accepted
  • Source Code
  • # include <cstdio>
    # define N 100000
    using namespace std;
    int set[N],id[N];
    int find(int pos)
    {
    	if(set[pos]==pos) return pos;
    	else return set[pos]=find(set[pos]);
    }
    void uni(int a,int b)
    {
    	set[find(a)]=find(b);
    }
    int main()
    {
    	int num;
    	while(scanf("%d",&num)!=EOF)
    	{
    		int c=num+1,n1=0,n2=0;
    		for(int i=1;i<N;i++) set[i]=i;
    		for(int i=1;i<=num;i++) id[i]=i;
    		char jud[5];
    		while(scanf("%s",jud)&&*jud!='e')
    		{
    			int a,b;
    			switch(*jud)
    			{
    			case 'c':
    				scanf("%d%d",&a,&b);
    				uni(id[a],id[b]);
    				break;
    			case 'd':
    				scanf("%d",&a);
    				id[a]=c++;
    				break;
    			case 'q':
    				scanf("%d%d",&a,&b);
    				if(find(id[a])==find(id[b])) n1++;
    				else n2++;
    				break;
    			};
    
    		}
    		printf("%d , %d\n",n1,n2);
    	}
    	return 0;
    }

posted on 2012-02-22 15:58 yzhw 阅读(272) 评论(0)  编辑 收藏 引用 所属分类: data struct


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜