welcome
0%

c-并查集

发表于 更新于 分类于
  1. 初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//初始化
int fa[maxn];
void init(int n)
{
    for(int i=0;i<=n;i++)
    fa[i]=i;
}
//查找父节点
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
// 合并
void merge(int i,int j)
{
    fa[find(i)]=find(j);
}

例题

  • 问题描述
    　　w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
    　　这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

　　如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

  • 输入格式
    　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
    　　接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
    　　接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

　　格子的编号一行一行，从上到下，从左到右编号。
　　比如：5 * 4 的小格子，编号：
　　1 2 3 4
　　5 6 7 8
　　9 10 11 12
　　13 14 15 16
　　17 18 19 20

  • 样例输入
    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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#define Max 1000000
using namespace std;
//const int Max = 1000000;
int fa[Max],n,m,k,temp=0;
void init()//初始化 
{
	
	for(int i=1;i<=n*m;i++){
		fa[i]=i;
	} 
}
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

void merge(int i,int j)
{
	fa[find(i)]=find(j);
}

int main()
{
	cin>>n>>m;
	init();
	cin>>k;
	for(int r=0;r<k;r++)
	{
		int i,j;
		cin>>i>>j;
		merge(i,j);
	}
	for(int i=1;i<=n*m;i++)
	{
		if(fa[i]==i) temp++;
	}
	cout<<temp;
}