基础算法题——#109. 并查集（字符串与并查集、快读）

逃离我推掉我的手 2022-12-20 01:28 201阅读 0赞

### [\#109. 并查集][109.] ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

又是一道并查集基础基础题~  
ps：不用快读也可过

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int mod=998244353;
    int u[4000010], n, m;
    ll ans=0;
    
    void read(int &n)
    { 
        char c='+';
    	n=0;
    	
    	//读去无意义的字符 
        while(c<'0'||c>'9') 
    		c=getchar();
    	//字符化整数 
        while(c>='0'&&c<='9') 
    		n=n*10+c-48,c=getchar();
    }
    
    void init(){ 
    	for(int i=0; i<n; i++)
    		u[i] = i;
    	return;
    }
    
    int find(int x){ 
    	if(u[x]==x) return x;
    	return u[x] = find(u[x]);
    }
    
    int main(){ 
    	read(n);read(m);
    	init();
    	while(m--){ 
    		int a, b, c, C, B;
    		read(a);read(b);read(c);
    		if(a==0){ 
    			B = find(b);
    			C = find(c);
    			if(B!=C)
    				u[B] = C;
    		}
    		else{ 
    			if(find(b)==find(c))
    				ans = (2*ans+1)%mod;
    			else
    				ans = (2*ans)%mod;
    		}
    	}
    	printf("%lld", ans);
    	
    	return 0;
    }

[109.]: https://www.luogu.com.cn/problem/U139791?contestId=36992
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/953b9141e85b48a99f09f7adf1680ef7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集算法

文章目录 1. 原理介绍 2. 并查集的应用 3. find()函数的定义与实现 4. 并查集的join函数

以你之姓@/ 2024年03月22日 15:46/ 0 赞/ 142 阅读

相关并查集基础

一、概念及其介绍并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个

曾经终败给现在/ 2024年03月16日 23:18/ 0 赞/ 109 阅读

相关并查集基础

一、概念及其介绍并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个

电玩女神/ 2024年03月16日 22:49/ 0 赞/ 130 阅读

相关算法14.并查集

算法|14.图相关算法 1.并查集（map版） package greedy; import java.util.HashMap;

朴灿烈づ我的快乐病毒、/ 2024年03月16日 10:42/ 0 赞/ 141 阅读

相关算法-并查集

算法-并查集转载声明本文大量内容系转载自以下文章，有删改，并参考其他文档资料加入了一些内容： [超有爱的并查集~][Link 1]

比眉伴天荒/ 2023年03月13日 06:51/ 0 赞/ 45 阅读

相关基础算法题——修复公路（并查集、kruskal）

[测试平台][Link 1] 题目背景 A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数N，和公路

青旅半醒/ 2023年02月27日 10:34/ 0 赞/ 62 阅读

相关基础算法题——#109. 并查集（字符串与并查集、快读）

[\109. 并查集][109.] ![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

逃离我推掉我的手/ 2022年12月20日 01:28/ 0 赞/ 202 阅读

相关算法随笔 — 树结构基础 — 并查集

并查集定义并查集是一种用来解决 `连通性` 的数据结构，抽象的方向不同会导致实现方式的不同。我们也可以用并查集来表示集合的关系。 1.快速查找(quick-fi

水深无声/ 2022年10月06日 05:53/ 0 赞/ 249 阅读

相关并查集--算法题

leetcode-200 islands 题意：给出一个二维数组，只包含 1/0 。1表示陆地，0表示水，求岛屿个数。例： input： 1 1 0

妖狐艹你老母/ 2022年01月12日 02:07/ 0 赞/ 301 阅读

相关算法：并查集

算法：并查集快速掌握理解算法　　在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合

ゝ一纸荒年。/ 2021年09月30日 11:30/ 0 赞/ 482 阅读