20 人解决，49 人已尝试。
20 份提交通过，共有 103 份提交。
6.4 EMB 奖励。
2130. Connected Components
单点时限: 2.0 sec
内存限制: 256 MB
Consider an undirected graph G formed from a large number of nodes connected by edges. G is said to be connected if there exists a path between any two distinct nodes in the graph. For example, consider the graph given below
The above graph is no connected, because there is no path from node A to node node D. However, it has two connected components, {A,B,C} and {D,E}. A connected component is a subset of nodes of the graph, such that there is a path between any two nodes in this subset, and no path to any node which is not in this set.
In this problem, you are required to determine the number of connected components of a given graph.
输入格式
The first line of the input contains n, the number of test cases. It is then followed by n test cases. The first line of the input contains a single upper case alphabet, representing the largest node name in the graph, followed by the number of edges in the graph. Each successive line contains a pair of upper case letters, denoting an edge in the graph.
输出格式
For each test case, output the number of connected components in the graph.
样例
Input
2 E 4 AB CE DB EC E 4 AB CE DB EC
Output
2 2
题目标签