【抽象并查集】CF1383A

冷不防 2024-03-16 09:43 89阅读 0赞

这居然是用并查集写，这谁能想到呀

[Problem - 1383A - Codeforces][]

题意：

![0ba32684d6324088884e3c010c91c872.png][]

思路：

本质上是去分析为什么经过操作之后步数会减少

事实上对于下面这个例子来说，a->b，b->c就不需要走a->c这条边了，因此步数减少了

这用并查集就能维护

![19735d24d334401b8f6858515f0173ec.png][]

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    string s,t;
    
    int N,ans=0;
    int f[mxn];
    
    int find(int x){
    	return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	if(f1!=f2) f[f1]=f2,ans++;
    }
    void solve(){
    	s.clear();
    	t.clear();
    	ans=0;
    	for(int i=1;i<=26;i++) f[i]=i;
    	cin>>N>>s>>t;
    	s=" "+s;
    	t=" "+t;
    	for(int i=1;i<=N;i++){
    		if(s[i]>t[i]){
    			cout<<-1<<'\n';
    			return;
    		}
    		join(s[i]-'a'+1,t[i]-'a'+1);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - 1383A - Codeforces]: https://codeforces.com/problemset/problem/1383/A
[0ba32684d6324088884e3c010c91c872.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/51f257b654f547e184816759890e1c94.png
[19735d24d334401b8f6858515f0173ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3a0486a8c88141dea5c54616a8ca69b3.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Artwork Gym - 101550A(并查集)

题目连接——][Link 1] 起初：这个题是关于图的**连通分量**的。对于连通分量，**bfs和dfs染色**的方式进行，判断连通分量的个数。也...

港控/mmm°/ 2024年04月18日 10:53/ 0 赞/ 81 阅读

相关【离线/并查集】CF1213 G

想起来好久没写题解了，随便写一下把感觉写多了div3后面的题就变得简单了，div3似乎没什么思维含量，甚至有时候能开出div3的2100.... 心血来潮写一下这个\18

待我称王封你为后i/ 2024年03月27日 18:33/ 0 赞/ 94 阅读

相关【并查集+贪心】CF Edu152 D

[Problem - D - Codeforces][] 题意： ![c58e721d6232468da7ab557993476cff.png][] ![5c9f617a

╰+哭是因爲堅強的太久メ/ 2024年03月26日 22:38/ 0 赞/ 76 阅读

相关【抽象并查集】CF1383A

这居然是用并查集写，这谁能想到呀 [Problem - 1383A - Codeforces][] 题意： ![0ba32684d6324088884e3c010c91c

冷不防/ 2024年03月16日 09:43/ 0 赞/ 90 阅读

相关离线+生成树+并查集——cf1213G

include<bits/stdc++.h> using namespace std; define N 200005 define ll lo

悠悠/ 2023年10月11日 09:09/ 0 赞/ 62 阅读

相关排序+并查集——cf1213F

/ 有向边(pi,pi+1)，形成链后进行dfs,求出dfs序一个联通块内的元素必须是同一个字符，如果最后的联通块个数<k,说明不行 /

红太狼/ 2023年10月11日 09:04/ 0 赞/ 63 阅读

相关 A - Wireless Network ——并查集

Think: 1知识点：并查集 2题意分析：初始状态已知n台电脑坐标，以及电脑连接的最大距离，进而，2种操作，操作O将电脑u连接到可连接集合，操作S询问电脑u和电脑v是

雨点打透心脏的1/2处/ 2022年06月12日 11:14/ 0 赞/ 138 阅读

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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