You are given nodeCount nodes labeled from 0 to nodeCount - 1.
You are also given a list of undirected edges. Each edge is provided as a string in links, and each string contains two node labels separated by a comma.
Your task is to count how many separate connected groups, also called connected components, exist in the undirected graph.
A connected group is a maximal set of nodes where every node can reach every other node in the same group by following zero or more edges. A node with no edges is considered its own connected group.
Method Signature
int countConnectedGroups(int nodeCount, List<String> links)
Parameters
nodeCount: The total number of nodes labeled from 0 to nodeCount - 1.links: A list of strings where each string represents one undirected edge.- Each string in
links has the format "u,v", where u and v are connected nodes.
Returns
- Return the number of connected groups in the graph.
Input Format
Since edges are provided as strings, each row in links must be parsed to extract the two connected nodes.
For example, the string "2,5" represents an undirected edge between node 2 and node 5.
Rules
- All edges are undirected.
- If
"a,b" exists, then node a is connected to node b, and node b is connected to node a.
- There are no duplicate edges.
- There are no self-loops.
- Nodes that do not appear in any edge still count as connected groups of size
1.
Constraints
1 ≤ nodeCount ≤ 1040 ≤ links.size() ≤ 2 * 104- Each
links.get(i) is a string in the format "u,v".
0 ≤ u < nodeCount0 ≤ v < nodeCountu != v- There are no duplicate edges in
links.
Examples
Example 1
countConnectedGroups(nodeCount = 5, links = ["0,1", "1,2", "3,4"])
Output: 2
Explanation: Nodes 0, 1, and 2 form one connected group. Nodes 3 and 4 form another connected group.
Example 2
countConnectedGroups(nodeCount = 6, links = ["0,3", "3,5", "1,2"])
Output: 3
Explanation: The connected groups are {0,3,5}, {1,2}, and {4}. Node 4 is isolated.
Example 3
countConnectedGroups(nodeCount = 4, links = ["0,1", "1,2", "2,3"])
Output: 1
Explanation: All nodes are connected directly or indirectly, so there is only one connected group.
Example 4
countConnectedGroups(nodeCount = 3, links = [])
Output: 3
Explanation: There are no edges, so every node is isolated and forms its own connected group.