本文主要是介绍【算法】Friends,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
描述
There are some people traveling together. Some of them are friends. The friend relation is transitive, that is, if A and B are friends, B and C are friends, then A and C will become friends too.
These people are planning to book some rooms in the hotel. But every one of them doesn’t want to live with strangers, that is, if A and D are not friends, they can’t live in the same room.
Given the information about these people, can you determine how many rooms they have to book at least? You can assume that the rooms are large enough.
输入
The first line of the input is the number of test cases, and then some test cases followed.
The first line of each test case contain two integers N and M, indicating the number of people and the number of the relationship between them. Each line of the following M lines contain two numbers A and B (1 ≤ A ≤ N , 1 ≤ B ≤ N , A ≠ B), indicating that A and B are friends.
You can assume 1 ≤ N ≤ 100, 0 ≤
这篇关于【算法】Friends的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!