837. 連通塊中點(diǎn)的數(shù)量

題目描述

給定一個(gè)包含 n 個(gè)點(diǎn)（編號(hào)為 1～n）的無(wú)向圖，初始時(shí)圖中沒(méi)有邊。

現(xiàn)在要進(jìn)行 m 個(gè)操作，操作共有三種：

1. C a b，在點(diǎn) a 和點(diǎn) b 之間連一條邊，a 和 b 可能相等；
2. Q1 a b，詢問(wèn)點(diǎn) a 和點(diǎn) b 是否在同一個(gè)連通塊中，a 和 b 可能相等；
3. Q2 a，詢問(wèn)點(diǎn) a 所在連通塊中點(diǎn)的數(shù)量；

輸入格式
第一行輸入整數(shù) n 和 m。

接下來(lái) m 行，每行包含一個(gè)操作指令，指令為 C a b，Q1 a b 或 Q2 a 中的一種。

輸出格式

對(duì)于每個(gè)詢問(wèn)指令 Q1 a b，如果 a 和 b 在同一個(gè)連通塊中，則輸出 Yes，否則輸出 No。

對(duì)于每個(gè)詢問(wèn)指令 Q2 a，輸出一個(gè)整數(shù)表示點(diǎn) a 所在連通塊中點(diǎn)的數(shù)量

每個(gè)結(jié)果占一行。

數(shù)據(jù)范圍

1≤n,m≤10⁵

輸入樣例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

輸出樣例：

Yes
2
3

維護(hù)size的并查集

#include<bits/stdc++.h> // 包含大多數(shù)標(biāo)準(zhǔn)庫(kù)
using namespace std;const int z=1e5+10; // 定義常數(shù)z為最大點(diǎn)數(shù)加10，用于數(shù)組大小int fa[z], size[z]; // fa數(shù)組存儲(chǔ)每個(gè)點(diǎn)的父節(jié)點(diǎn)，size數(shù)組存儲(chǔ)每個(gè)連通塊的大小// 并查集的查找函數(shù)，用于查找元素i的根節(jié)點(diǎn)，并執(zhí)行路徑壓縮
int find(int i) {if(fa[i] != i) fa[i] = find(fa[i]); // 路徑壓縮，遞歸地將fa[i]更新為根節(jié)點(diǎn)return fa[i]; // 返回根節(jié)點(diǎn)
}// 主函數(shù)
int main() {int n, m; // n表示點(diǎn)的數(shù)量，m表示操作的數(shù)量cin >> n >> m; // 輸入點(diǎn)的數(shù)量和操作的數(shù)量// 初始化并查集for (int i = 1; i <= n; i++) {fa[i] = i; // 每個(gè)點(diǎn)的父節(jié)點(diǎn)初始化為自己size[i] = 1; // 每個(gè)點(diǎn)所在連通塊的大小初始化為1}// 循環(huán)處理m個(gè)操作while (m--) {string s; // 存儲(chǔ)操作類型cin >> s; // 輸入操作類型// 根據(jù)不同的操作類型進(jìn)行操作if(s == "C") { // 連接操作int a, b;cin >> a >> b; // 輸入要連接的兩個(gè)點(diǎn)的編號(hào)if(find(a) == find(b)) continue; // 如果已經(jīng)在同一個(gè)連通塊中，無(wú)需操作// 否則，合并兩個(gè)連通塊size[find(b)] += size[find(a)]; // 更新根節(jié)點(diǎn)的連通塊大小fa[find(a)] = find(b); // 將一個(gè)點(diǎn)的根節(jié)點(diǎn)連接到另一個(gè)點(diǎn)的根節(jié)點(diǎn)} else if(s == "Q1") { // 查詢操作1，詢問(wèn)兩個(gè)點(diǎn)是否連通int a, b;cin >> a >> b; // 輸入要查詢的兩個(gè)點(diǎn)的編號(hào)if(find(a) == find(b)) cout << "Yes" << endl; // 如果根節(jié)點(diǎn)相同，輸出Yeselse cout << "No" << endl; // 否則，輸出No} else { // 查詢操作2，詢問(wèn)連通塊的大小int a;cin >> a; // 輸入要查詢的點(diǎn)的編號(hào)cout << size[find(a)] << endl; // 輸出該點(diǎn)所在連通塊的大小}}return 0;
}

在這段代碼中，主要用到了兩個(gè)全局?jǐn)?shù)組fa和size。fa數(shù)組用來(lái)表示每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，初始化時(shí)每個(gè)節(jié)點(diǎn)都是自己的父節(jié)點(diǎn)。size數(shù)組用來(lái)表示以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的連通塊的大小，初始化為1。每次合并連通塊時(shí)，會(huì)更新這兩個(gè)數(shù)組的信息。

find函數(shù)是并查集的核心，用于查找節(jié)點(diǎn)的根節(jié)點(diǎn)，并在這個(gè)過(guò)程中進(jìn)行路徑壓縮。

在main函數(shù)中，代碼首先接收輸入的節(jié)點(diǎn)數(shù)和操作數(shù)，然后通過(guò)循環(huán)處理每一條操作指令。指令分為三種類型，分別對(duì)應(yīng)代碼中的三個(gè)分支。

• C操作將兩個(gè)節(jié)點(diǎn)連接在一起，如果它們不在同一個(gè)連通塊中，會(huì)合并它們所在的連通塊，并更新連通塊大小。
• Q1操作判斷兩個(gè)節(jié)點(diǎn)是否在同一個(gè)連通塊中，輸出結(jié)果。
• Q2操作輸出給定節(jié)點(diǎn)所在連通塊的大小。

這個(gè)程序?qū)?yīng)了題目描述中的需求，它可以有效地處理大量的連通性查詢和連通塊大小查詢。