In an undirected graph, a connected component or component is a maximal connected subgraph. Two vertices are in the same connected component if and only if there exists a path between them. In a drawing of a graph, the connected components can each be drawn separately with empty space between them. A nonempty connected graph has one connected component.
Given an undirected graph, output the number of connected components of this graph.
There are several test cases, each test case start with two number v and e, denoting number of nodes and edges, where v<=1000. Following are e lines, each line contains two integer x and y, denoting there's an edge between x and y. The node is numbered from 1 to v. The input ends by v=0 and e=0.
For each test case, output the number of connected components.
1 1 1 1 3 3 1 2 3 2 2 1 5 5 5 2 3 3 1 5 4 2 1 2 0 0
1 1 2
Detph First Search
http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|