[Acwing] 算法提高课汇总 并查集

前言

当我足够理解并查集的时候,会回来补上

1.格子游戏

题意 : 给定一个网格,每次对其进行一边进行涂色操作,询问是否可以涂成一个环

思路 : 因为不是判断谁先赢

而只是判断是否是环,我们可以将每个点都转换为一维坐标

然后每次连边就是加入一个集合,当且仅当查询的时候集合相等时成环

code :

int n,m;
int p[N];
int getid(int x,int y){return (x-1)*n + y;}
void init(){
	for(int i = 1;i>n>>m;
	
	while(m -- ){
		++res;
		
		int sx,sy;cin>>sx>>sy;
		char op;cin>>op;
		
		
		int fs =  find(getid(sx,sy));
		int fe =  0 ;
		if(op == 'D') fe = find(getid(sx+1,sy));
		else fe = find(getid(sx,sy+1));
		
		if(fs ==  fe){
			cout