网站关键词建设,推广自己的网站需要怎么做,网站开发公司广告word,基于html的个人网站的设计与实现论文[蓝桥杯 2017 国 C] 合根植物
题目描述
w 星球的一个种植园#xff0c;被分成 m n m \times n mn 个小格子#xff08;东西方向 m m m 行#xff0c;南北方向 n n n 列#xff09;。每个格子里种了一株合根植物。
这种植物有个特点#xff0c;它的根可能会沿着南北…[蓝桥杯 2017 国 C] 合根植物
题目描述
w 星球的一个种植园被分成 m × n m \times n m×n 个小格子东西方向 m m m 行南北方向 n n n 列。每个格子里种了一株合根植物。
这种植物有个特点它的根可能会沿着南北或东西方向伸展从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象你能说出这个园中一共有多少株合根植物吗
输入格式
第一行两个整数 m m m n n n用空格分开表示格子的行数、列数 1 m , n 1000 1m,n1000 1m,n1000。
接下来一行一个整数 k k k表示下面还有 k k k 行数据 ( 0 k 1 0 5 ) (0k10^5) (0k105)。
接下来 k k k 行每行两个整数 a a a b b b表示编号为 a a a 的小格子和编号为 b b b 的小格子合根了。
格子的编号一行一行从上到下从左到右编号。
比如 5 × 4 5 \times 4 5×4 的小格子编号
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20输出格式
一行一个整数表示答案
样例 #1
样例输入 #1
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样例输出 #1
5提示
样例解释 时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛
考查知识点并查集 本题解题关键 找到多少珠合根植物找到根的数目 也就是 fa[i]i 初始化
void init(int n)
{for(int i1;in;i){fa[i]i;}
}查找
int find(int i)
{if(ifa[i])return i;elsereturn fa[i]find(fa[i]);}
合并
void unio(int x,int y)
{int x_1find(x);int y_1find(y);if(x_1!y_1)fa[x_1]y_1;
}在这定义函数不能用union:它是关键字
完整代码
#include bits/stdc.h
#define int long long
using namespace std;
const int N1000001;
int fa[N];void init(int n)
{for(int i1;in;i){fa[i]i;}
}
int find(int i)
{if(ifa[i])return i;elsereturn fa[i]find(fa[i]);}void unio(int x,int y)
{int x_1find(x);int y_1find(y);if(x_1!y_1)fa[x_1]y_1;
}
signed main()
{int m,n;cinmn;int wm*n;init(w);int k;cink;int o,p;int ans0;for(int i1;ik;i){cinop;unio(o,p);}for(int i1;iw;i){if(fa[i]i)ans;}coutans;return 0;
}
