並查集 合根植物

2022-11-24 21:41:19 字數 903 閱讀 7530

資源限制

時間限制:2.0s   記憶體限制:256.0mb

問題描述

w星球的一個種植園,被分成 m * n 個小格子(東西方向m行,南北方向n列)。每個格子裡種了一株合根植物。

這種植物有個特點,它的根可能會沿著南北或東西方向伸展,從而與另一個格子的植物合成為一體。

如果我們告訴你哪些小格子間出現了連根現象,你能說出這個園中一共有多少株合根植物嗎?

輸入格式

第一行,兩個整數m,n,用空格分開,表示格子的行數、列數(1樣例輸入

5 416

2 31 5

5 94 8

7 89 10

10 11

11 12

10 14

12 16

14 18

17 18

15 19

19 20

9 13

13 17

樣例輸出

5樣例說明

其合根情況參考下圖

**:

#include#define endl '\n' 

using

namespace

std;

const

int n = 1e6+5

;typedef

long

long

ll;int

res;

intfat[n];

int find(int

x)

int i =x;

while(i!=r)

returnr;}

void merge(int a,int

b)else

}int

main()

cout

return0;

}

並查集,合根植物

合根植物題目 一開始看到這個題的時候我剛學搜尋不就,一想不就是個搜尋嗎,有什麼難的,然後直接就開始搜了,然後就很悲慘的。超時,超時,超時。再後來就知道了這個 最好先看一下我的另一篇部落格再來看這個會看的更明白一點。這個題的解題思路和那個什麼江湖門派合併 另一篇並查集 差不多,每個植物看成是一個人,每...

藍橋杯 歷屆試題 合根植物

問題描述 w星球的一個種植園,被分成 m n 個小格子 東西方向m行,南北方向n列 每個格子裡種了一株合根植物。這種植物有個特點,它的根可能會沿著南北或東西方向伸展,從而與另一個格子的植物合成為一體。如果我們告訴你哪些小格子間出現了連根現象,你能說出這個園中一共有多少株合根植物嗎?輸入格式 第一行,...

BZOJ4668 冷戰 按秩合併並查集

有 n 個點,m 個操作,每次連線兩個點,或者詢問某兩個點最早是在什麼時刻開始連通的 考慮按秩合併並查集 對於每個結點,記錄它到它父親的邊的權值為時間戳 詢問時,類似樸素 lca 暴力往上跳即可 include using namespace std define int long long con...