noj 1087 并查集.txt

ACM资料大集合

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

//G++ and GCC
#define NMAX 100005

typedef struct line
{
	int a;//线连接的两个点
	int b;
	bool has;//这条线是否没被删去
}line;

typedef struct act
{
	char kind;//操作类型，删除还是查询
	int aa;//操作的两个点
	int bb;
}act;

line ll[NMAX];
act ac[NMAX];
bool ans[NMAX];
int fa[NMAX];
int rank[NMAX];

int cmp(const void *x,const void *y)
{
	if(((line *)x)->a==((line *)y)->a)
		return ((line *)x)->b-((line *)y)->b;
	else return  ((line *)x)->a-((line *)y)->a;
}

int search(line key,int num)
{
	line *q;
	q=(line *)bsearch(&key,ll+1,num,sizeof(ll[1]),cmp);
	return q-ll;
}

void init(int num)
{
	int i;
	for(i=1;i<=num;i++) 
	{
		rank[i]=1;
		fa[i]=-1;
	}
}

int find(int c)
{	//查询该元素的代表元
	int tt,root=c;
	while(fa[root]!=-1) root=fa[root];
	while(fa[c]!=-1)
	{	//查询的同时压缩路径
		tt=fa[c];
		fa[c]=root;
		c=tt;
	}
}

bool isconn(int c,int d)
{
	if(find(c)==find(d)) return true;
	else return false;
}

void add(int c,int d)
{
	//合并的时候，看的是代表元
	c=find(c);
	d=find(d);
	if(c!=d)
	{	//还是注意c=d的情况，会有fa[c]=c，死循环的说
		if(rank[c]<rank[d])
		{
			fa[c]=d;
			rank[d]+=rank[c];
		}
		else
		{
			fa[d]=c;
			rank[c]+=rank[d];
		}
	}
}

void print()
{
	int i;
	for(i=1;i<=6;i++)
	{
		printf("(%d %d %d)",ll[i].a,ll[i].b,ll[i].has);
	}
	printf("\n");
}

void solve(int num,int fnum,int cnum)
{
	//说下solve的思路
	//总体思路 倒着做+并查集
	//solve(1) 对边排序，方便在solve(2)里根据操作对应的点找到这条边
	//solve(2) 将操作顺次编列一编，如果进行的是删除操作，则找出这条边，将其置被删除符号
	//solve(3) 用没被操作删除的边，进行并查集的合并操作
	//solve(4) 将操作逆次编列一编，如果是删除操作，则做并查集的合并，否则做并查集的查询,同时把查询的结果存在ans数组里
	//solve(5) 将ans数组逆次输出
	int i,xuhao,k;
	line temp;
//	printf("solve (1)\n");
	qsort(ll+1,fnum,sizeof(ll[1]),cmp);
//	print();
//	printf("solve (2)\n");
	for(i=1;i<=cnum;i++)
	{
		if(ac[i].kind=='D')
		{
			temp.a=ac[i].aa;
			temp.b=ac[i].bb;
//			printf("temp.a=%d temp.b=%d\n",temp.a,temp.b);
			xuhao=search(temp,fnum);
			ll[xuhao].has=false;
		}
	}
//	printf("solve (3)\n");
	for(i=1;i<=fnum;i++)
	{
		if(ll[i].has==true) add(ll[i].a, ll[i].b);
	}
//	printf("solve (4)\n");
	for(i=cnum,k=0;i>=1;i--)
	{
		if(ac[i].kind=='D') add(ac[i].aa, ac[i].bb);
		else 
		{
			 ans[++k]=isconn(ac[i].aa, ac[i].bb);
		}
	}
//	printf("solve (5)\n");
	for(i=k;i>=1;i--)
	{
		if(ans[i]==true) printf("C\n");
		else printf("D\n");
	}
}

int main()
{
	int t,num,fnum,cnum,i,x,y;
	char ch[3];
	scanf("%d %d",&num,&fnum);
	init(num);
	for(i=1;i<=fnum;i++)
	{
		scanf("%d %d",&x,&y);
		if(x>y)
		{
			t=y;
			y=x;
			x=t;
		}
		ll[i].a=x;
		ll[i].b=y;
		ll[i].has=true;
	}
	scanf("%d",&cnum);
	for(i=1;i<=cnum;i++)
	{
		scanf("%s",&ch);
		scanf("%d %d",&x,&y);
		if(x>y)
		{
			t=y;
			y=x;
			x=t;
		}
		ac[i].kind=ch[0];
		ac[i].aa=x;
		ac[i].bb=y;
	}
	solve(num,fnum,cnum);
	return 0;
}


========================================
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define NMAX 100005
#define true 1
#define false 0
typedef struct line
{
	int a;
	int b;
	int has;
}line;

typedef struct act
{
	char kind;
	int aa;
	int bb;
}act;

line ll[NMAX];
act ac[NMAX];
int ans[NMAX];
int fa[NMAX];
int rank[NMAX];

int cmp(const void *x,const void *y)
{
	if(((line *)x)->a==((line *)y)->a)
		return ((line *)x)->b-((line *)y)->b;
	else return  ((line *)x)->a-((line *)y)->a;
}

int search(line key,int num)
{
	line *q;
	q=(line *)bsearch(&key,ll+1,num,sizeof(ll[1]),cmp);
	return q-ll;
}

void init(int num)
{
	int i;
	for(i=1;i<=num;i++) 
	{
		rank[i]=1;
		fa[i]=-1;
	}
}

int find(int c)
{
	int tt,root=c;
	while(fa[root]!=-1) root=fa[root];
	while(fa[c]!=-1)
	{
		tt=fa[c];
		fa[c]=root;
		c=tt;
	}
}

int isconn(int c,int d)
{
	if(find(c)==find(d)) return true;
	else return false;
}

void add(int c,int d)
{
	c=find(c);
	d=find(d);
	if(c!=d)
	{
		if(rank[c]<rank[d])
		{
			fa[c]=d;
			rank[d]+=rank[c];
		}
		else
		{
			fa[d]=c;
			rank[c]+=rank[d];
		}
	}
}

void print()
{
	int i;
	for(i=1;i<=6;i++)
	{
		printf("(%d %d %d)",ll[i].a,ll[i].b,ll[i].has);
	}
	printf("\n");
}

void solve(int num,int fnum,int cnum)
{
	int i,xuhao,k;
	line temp;
//	printf("solve (1)\n");
	qsort(ll+1,fnum,sizeof(ll[1]),cmp);
//	print();
//	printf("solve (2)\n");
	for(i=1;i<=cnum;i++)
	{
		if(ac[i].kind=='D')
		{
			temp.a=ac[i].aa;
			temp.b=ac[i].bb;
//			printf("temp.a=%d temp.b=%d\n",temp.a,temp.b);
			xuhao=search(temp,fnum);
			ll[xuhao].has=false;
		}
	}
//	printf("solve (3)\n");
	for(i=1;i<=fnum;i++)
	{
		if(ll[i].has==true) add(ll[i].a, ll[i].b);
	}
//	printf("solve (4)\n");
	for(i=cnum,k=0;i>=1;i--)
	{
		if(ac[i].kind=='D') add(ac[i].aa, ac[i].bb);
		else 
		{
			 ans[++k]=isconn(ac[i].aa, ac[i].bb);
		}
	}
//	printf("solve (5)\n");
	for(i=k;i>=1;i--)
	{
		if(ans[i]==true) printf("C\n");
		else printf("D\n");
	}
}

int main()
{
	int t,num,fnum,cnum,i,x,y;
	char ch[3];
	scanf("%d %d",&num,&fnum);
	init(num);
	for(i=1;i<=fnum;i++)
	{
		scanf("%d %d",&x,&y);
		if(x>y)
		{
			t=y;
			y=x;
			x=t;
		}
		ll[i].a=x;
		ll[i].b=y;
		ll[i].has=true;
	}
	scanf("%d",&cnum);
	for(i=1;i<=cnum;i++)
	{
		scanf("%s",&ch);
		scanf("%d %d",&x,&y);
		if(x>y)
		{
			t=y;
			y=x;
			x=t;
		}
		ac[i].kind=ch[0];
		ac[i].aa=x;
		ac[i].bb=y;
	}
	solve(num,fnum,cnum);
	return 0;
}