【并查集入门】HDU1232——通畅工程

【并查集入门】HDU1232——畅通工程

来源：点击打开链接

看KMP看烦了，来一道并查集入门吧。并查集其实是一种简单的数据结构，采用树的方式存储，数组中读取的方式是通过父亲节点来进行查找，顾名思义，取该名的原因是因为可并可查。常用来解决一种求两两关系之间的总类数的模型，实现也十分美观，没有什么难懂的地方。状态压缩也非常浅显，待了解深入后可以小做总结以备忘之。

这个题是标准的并查集模板，结构清晰，基本都不用讲，很快就可以自己练会。没有状态压缩的并查集有个特点就是卡时间，所以尽量使用scanf,printf，题目也会给予透露的，毕竟时间充裕的问题暴个搜完全解决了。。

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;

int numpack[1005];

int search_father(int num)  //查 
{
	int result=num;
	while(result!=numpack[result])
	{
		result=numpack[result];
	}
	
	return result;
}

void merge(int a,int b)  //并 
{
	int ka=search_father(a);
	int kb=search_father(b);
	if(ka!=kb)
	{
		numpack[ka]=kb;
	}
}

int main()
{
	int city,road;
	while(scanf("%d",&city))
	{
		if(city==0)
			return 0;
		else
		{
			scanf("%d",&road);
		}
		for(int i=1;i<=city;i++)//序号从1开始，WA了一次 
		{
			numpack[i]=i;
		}
		
		for(int j=1;j<=road;j++)
		{
			int start,end;
			scanf("%d%d",&start,&end);
			merge(start,end);//并 
		}
		
		int count=0;
		for(int k=1;k<=city;k++)
		{
			if(numpack[k]==k)
				count++;
		}
		
		printf("%d\n",count-1);
		
		
	}
	return 0;
}