[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; i++ )p[i] = i;
}
int find(int x){
	if(p[x]!=x) return p[x] = find(p[x]);
	return p[x];
}
void solve(){
	init();
	int res = 0 ;
	
	cin>>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<