本文共 1288 字，大约阅读时间需要 4 分钟。

题目链接:

问题描述

　　w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。

输入格式

　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。

样例输入

5 4

16

2 3

1 5

5 9

4 8

7 8

9 10

10 11

11 12

10 14

12 16

14 18

17 18

15 19

19 20

9 13

13 17

样例输出

5

样例说明

其合根情况参考下图

解题思路

一看就是并查集。。。

#include 
   
    #include 
    
     int f[1000010], vis[1000010];int getf(int v){    if (f[v] != v)        return f[v] = getf(f[v]);    return v;}void merge(int u, int v){    int t1 = getf(u);    int t2 = getf(v);    if (t1 != t2)        f[t2] = t1;}int main(){    int n, m, t, a, b, all, ans;    while (~scanf("%d%d", &n, &m))    {        ans = 0;        all = n * m;        for (int i = 0; i < all; i++)            f[i] = i;        scanf("%d", &t);        while (t--)        {            scanf("%d%d", &a, &b);            merge(a, b);        }        for (int i = 0; i < all; i++)            vis[getf(i)] = 1;        for (int i = 0; i < all; i++)            if (vis[i])                ans++;        printf("%d\n", ans);    }    return 0;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/86768299 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！