LibreOJ #109. 並查集

• 記憶體限制：256 MiB
• 時間限制：2000 ms
• 標準輸入輸出
• 題目類型：傳統
• 評測方式：文本比較
  上傳者： 匿名

【題目描述】

這是一道模板題。

維護一個 nnn 點的無向圖，支持：

加入一條連接 uuu 和 vvv 的無向邊
查詢 uuu 和 vvv 的連通性
由於本題數據較大，因此輸出的時候採用特殊的輸出方式：用 000 或 111 代表每個詢問的答案，將每個詢問的答案依次從左到右排列，把得到的串視為一個二進位數，輸出這個二進位數 mod 998244353\text{mod} ~ 998244353mod 998244353 的值。

【輸入格式】

第一行包含兩個整數 n,mn,mn,m，表示點的個數和操作的數目。

接下來 mmm 行每行包括三個整數 op,u,v\text{op},u,vop,u,v。

如果 op=0\text{op} = 0op=0，則表示加入一條連接 uuu 和 vvv 的無向邊；
如果 op=1\text{op} = 1op=1，則表示查詢 uuu 和 vvv 的連通性。

【輸出格式】

一行包括一個整數表示答案。

樣例

• 樣例輸入

3 6
1 1 0
0 0 1
1 0 1
1 1 2
0 2 1
1 2 1

• 樣例輸出

5

• 樣例解釋

答案串為 0101。

【數據範圍與提示】

n≤4000000,m≤8000000n≤4000000,m≤8000000n≤4000000,m≤8000000

By zyz

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int inf = 998244353;
int fa[4000010],size[4000010],bin[8000010],n,m,ans;
int readint(){            //讀入優化
    int Num;
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    Num=ch-'0';
    while((ch=getchar())>='0'&&ch<='9'){
        Num=Num*10+ch-'0';
    } 
    return Num;
}
int equal(int x,int y)            //判斷是否相等
{
    if(x==y) return 1;
    else return 0;
}
int get(int x)
{
    if(fa[x]==x)return x;
    else return fa[x] = get(fa[x]);            //路徑壓縮
}
void merge(int a,int b)        //合併兩個集合
{
    int aa,bb;
    aa=get(a);
    bb=get(b);
    if(aa!=bb)
    {
                //這裡很重要！！！
        if(size[aa]>=size[bb])        //將子節點少的集合合併到子節點多的集合，省時間
        {
            fa[aa]=bb;                
            size[aa] += size[bb];
        }
        else
        {
            fa[bb]=aa;
            size[bb] += size[aa];
        }
    } 
}
int main()
{
    int op,u,v;
    n=readint();
    m=readint();
    for(int i=0;i<n;i++) fa[i]=i;        //一開始每個點都為一個集合，父節點是自己
    for(int i=1;i<=m;i++)
    {
        op=readint();
        u=readint();
        v=readint();
        if(op==0) merge(u,v);
        else{
            ans = (ans*2 + equal(get(u),get(v)))%inf;     //這裡直接用get(u)==get(v)測試時出錯，所以寫了個int型的函數判斷
        }                                                                            //當然也可以用if判斷，ans++
    }
    cout<<ans%inf;
    return 0;
}