|
呐，有点困了，不过没关系，不妨碍我敲代码，梳理思路。没错，这一篇还是并查集！！！！/*小爷我今天跟他杠上了，U1S1，并查集其实就是个板子（bushi，额...大部分！我求求别虐我）*/那么我们来看看这一道并查集又让我们干什么吧。题目如下，请认真阅读哦。
这是一道模板题。
维护一个?n?点的无向图，支持：
- 加入一条连接?u?和?v?的无向边
- 查询?u?和?v?的连通性
由于本题数据较大，因此输出的时候采用特殊的输出方式：用?0?或?1代表每个询问的答案，将每个询问的答案依次从左到右排列，把得到的串视为一个二进制数，输出这个二进制数mod?998244353?的值。
请务必使用快读。
输入格式
第一行包含两个整数?n,m，表示点的个数和操作的数目。
接下来?mm?行每行包括三个整数op,u,v。
- 如果op=0，则表示加入一条连接?u?和?v?的无向边；
- 如果op=1，则表示查询?u?和?v?的连通性。
?输出格式
一行包括一个整数表示答案。
样例
| Input | Output |
|---|
3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1 | 5 |
答案串为?0101。
?欸嘿！乍一看，是不是觉得，**这题好高级！！为啥我看不懂！！！/*不会吧不会吧，不会只有我一个人这么认为吧，不行不行，呜呜呜你们必须让着我！没关系，就让我大聪明！！！！来为大家进行解释一下吧*/
其实题目的意思很简单。首先给出两个数字n,m，n的意思就是一共有n个点，而m代表进行m次操作。接下来会有m行来进行操作。每一行又会有三个数字，op，u，v。如果op=0，那么就是要建立后面两位数的联系。op=1就是询问后面那两个数字是否有联系。为了方便，我们的结果就用0.1表示。如果那两个数字有联系我们就输出1，否则的话就输出0。为了方便，01组合起来，变成二进制数就是我们最后的答案，然后把二进制数字转化过来，但是由于这道题目的数据范围很大，所以转化过来就会很大，所以我们还要对他进行取模。这就是题目的大概意思。怎么样，这样一讲，是不是感觉豁然开朗，这不就是个并查集嘛!对吧。题目搞明白了，那么我们应该如何解题呢？
既然我们说这道题目是并查集，那么不出意外肯定还是要从并查集下手。并查集的核心依旧是（找+并）首先，找，找什么？找他俩是否有关系。并，又是并什么？把有关系的数字并到一个集合里去。这样一讲，是不是感觉自己犹如醍醐灌顶，云云雾雾的呢！所以，对于题目的初步分析就是这样，这样的话我们不难得出那个01组合的一长串数字。不过吼，得到那个一长串数字，你打算怎么办呢？不会真的有人打算得出了那么一长串数字然后再转化为十进制吧。不会吧不会吧/阴阳怪气MAX那样的话，一是会很麻烦，二是会增加时间，三是有简单的我们为什么不用呢？当我们得出答案的时候要么是0，要么是1。这样的话，想一想如果是二进制转换该如何变呢？比如说0101，最开始的时候sum=0，是不是就应该是sum*=2那第一个答案是0，转换过来肯定还是0？第二个是1，如果是二进制那应该是1*2的三次方，但是我们现在是反过来的，所以就应该sum++，同时sum*=2。这样归纳一下的话，转为二进制就应该，当答案是1的时候，自加，然后*2。如果是0的话，就直接*2。到这里我们的代码就差不多啦，千万要记得取模哦！！！！！
好啦，我的分析就这些叭！翠花！上代码！
#include<bits/stdc++.h>
#define N 9000000
#define mod 998244353
using namespace std;
int parent[N],n,m,a,b,c;
void init()
{
for(int i=1;i<=n;i++)
{
parent[i]=i;
}
}
int find(int x)
{
if(parent[x]==x)
{
return x;
}else {
parent[x]=find(parent[x]);
return parent[x];
}
}
void uni(int x,int y)
{
int dx=find(x);
int dy=find(y);
if(dx!=dy)
{
parent[dy]=dx;
}
}
int main()
{
long long sum=0;
scanf("%d %d",&n,&m);
init();
while(m--)
{
scanf("%d %d %d",&a,&b,&c);
if(a==0)
{
uni(b,c);
}
else if(a==1)
{
if(find(b)==find(c))
{
sum*=2;
sum++;
sum%=mod;
}else {
sum*=2;
sum%=mod;
}
}
}printf("%lld\n",sum);
return 0;
}
对啦，最后的最后呢，再跟大家分享一下，我写这份代码的时候的一些小细节。首先就是呢，让我WA了好几发的初始化。虽然数组初始化是写在外面的，但是一定要记得把函数调用加在主函数里面，还有就是我这里的数组初始化是要用到n的，所以哦，一定要放在读入n的下面。还有呢，就是注意看数据范围。不然小心RE爱上你~~~
嗯，就是这样，喵！困了困了，写完了去睡觉。还有问题的话私信或者评论嗷！回见！
哦对了，如果你真的不明白那个二进制转换，咱这边呢，是建议您可以尝试一下手动模拟。一定会哭着喊着再也不想模拟的收获颇丰的！（想当初，我可是手模dfs全排列模拟到哭的小孩）
|