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

逃离我推掉我的手 2022-12-20 01:28 146阅读 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 条评论，146人围观）

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

相关阅读

相关并查集算法

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

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

相关并查集基础

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

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

相关并查集基础

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

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

相关算法14.并查集

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

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

相关算法设计——并查集

【蓝桥杯】历届试题合根植物问题描述　　w星球的一个种植园，被分成 m \ n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。　　这

拼搏现实的明天。/ 2023年10月05日 17:32/ 0 赞/ 38 阅读

相关 Java算法——并查集

功能并查集是管理多个集合的算法，其功能包括集合的合并、集合内或集合间的查询。背景在中国古代，人们都比较重视血缘传承，几乎每家都至少会有一个男孩，后人总会牢记

川长思鸟来/ 2023年01月11日 09:07/ 0 赞/ 188 阅读

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

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

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

相关并查集算法理解

并查集算法理解并查集主要就是解决判断两个点两个物体是否有关系，如在最小生成树kr

清疚/ 2022年05月17日 07:42/ 0 赞/ 209 阅读

相关并查集--算法题

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

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

相关算法：并查集

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

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