学步园

• 问题描述
• Hungar has bought some farms.There is a river near the
  farm. It was found that linking these farms is more conducive for
  hungar. Therefore, he need to calculate that the minimum number of
  waterway he should build to connect all the farms, either connecting
  directly or not directly.There is not existing a waterway between river
  and farm,so you should also connecting them.
• 输入
• Input until EOF.
  For each case:
  First line: two non-negative integers M (1<=M<= 500) and N(1<=N<=500), M means the number of farms, from 1 to M.
  The next N lines: each line have two numbers A, B represents the existing waterway number.
• 输出
• Print the number of waterway in one line.
• 样例输入

• 4 2
  1 3
  4 3
  2 2
  1 2
  1 2
  

• 样例输出

• 2
  1
  

• 提示

• 无

• 来源

• hungar

并查集。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>

using namespace std;

int father[505];

int find(int x)
{
	if(x!=father[x])
	  father[x]=find(father[x]);
    return father[x];
}

int main()
{
	int m,n;
	while(~scanf("%d%d",&m,&n))
	{
		for(int i=0;i<=m;i++)
		  father[i]=i;
        int u,v,cnt=0;
        while(n--)
        {
        	scanf("%d%d",&u,&v);
        	int x=find(u);
        	int y=find(v);
        	if(x!=y)
        	  father[x]=y;
        }
        for(int i=1;i<=m;i++)
          if(i==father[i])
            cnt++;
        printf("%d\n",cnt);
	} 
	return 0;
}