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

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

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

相关阅读

相关并查集基础

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

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

相关并查集基础

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

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

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

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

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

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 258 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 255 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 322 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 314 阅读

相关并查集--算法题

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

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

相关算法：并查集

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

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

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 514 阅读