Hdu1232 unimpeded project (and collection)

Topic link

http://acm.hdu.edu.cn/showproblem.php?pid=1232

Question

Problem Description

A province investigates the traffic condition of the town , Get the statistics of existing urban roads , The towns directly connected by each road are listed in the table . provincial government “ Unimpeded works ” The goal is to make transportation possible between any two towns in the province （ But there's not necessarily a direct link , As long as they can reach each other indirectly through the road ）. Ask how many roads need to be built at least ？

Input

The test input contains several test cases . The... Of each test case 1 Line gives two positive integers , They are the number of towns N ( < 1000 ) And the number of roads M; And then M Row correspondence M road , Each line gives a pair of positive integers , They are the numbers of the two towns directly connected by the road . For the sake of simplicity , Town from 1 To N Number .
Be careful : There can be many roads between the two cities , in other words
3 3
1 2
1 2
2 1
This input is also legal
When N by 0 when , End of input , The use case is not processed .

Output

For each test case , stay 1 The output of the line is the minimum number of roads to be built .

Solve

Obviously, it can be seen that this is a deformation of the minimum spanning tree , It's easier ^_^

Take a look at this article first ： Two algorithms of minimum spanning tree

Among them Kruskal Algorithms are commonly used , But this problem is not so troublesome , Simply combine and search sets ~

We can know to get through n Nodes , At the very least n-1 side , So define res = n - 1

According to this condition , Then use and search the set to judge whether each read edge has been connected ：

If it is already connected , You don't need to do anything ;

If there is no connection , Then read in the side and connect , The number of roads to be built will also be reduced by one (res--)

I got it after reading res That's the result

AC Code

#include <iostream>
#include <cstring>
#define N 1000
using namespace std;
int fa[N+1], n, m;
// Find the root node  
int find(int x)
{
	if(fa[x] == x) 
		return x;
	else
		return fa[x] = find(fa[x]);
}
int main(void)
{
	while(cin >>n && n != 0)
	{
		cin >>m;
		// Initialize and query set  
		for(int i = 1; i <= n; i++) fa[i] = i;
		int res = n - 1;
		
		for(int i = 1; i <= m; i++){
			int x, y;  cin >>x >>y;
			int dx = find(x);  int dy = find(y);
			// Already connected   Just skip , Unconnected   Connect and record  
			if(dx == dy) continue;
			fa[dx] = dy;
			res--;
		}
		cout <<res <<endl;
	}
	return 0;
}