#K3921. Collaboration Groups
Collaboration Groups
Collaboration Groups
You are given M employees numbered from 1 to M. There are N bidirectional collaborations among these employees. Each collaboration connects two employees directly. A collaboration group is defined as a set of employees who are connected directly or indirectly through a series of collaborations.
Your task is to determine the number of distinct collaboration groups among the employees.
Note: If an employee does not participate in any collaboration, they are considered as a separate group.
The problem can be formally represented as finding the number of connected components in an undirected graph. In mathematical terms, if we denote the set of employees as \(V\) and the set of collaborations as \(E\), you are required to find the number of connected components in the graph \(G(V, E)\).
inputFormat
The input is read from stdin
and has the following format:
- The first line contains two space-separated integers M and N, where M (\(1 \leq M \leq 10^5\)) is the number of employees and N (\(0 \leq N \leq 10^5\)) is the number of collaborations.
- The next N lines each contain two space-separated integers a and b (\(1 \leq a, b \leq M\)) indicating that employee a collaborates with employee b.
outputFormat
Output a single integer to stdout
representing the number of collaboration groups.
5 3
1 2
2 3
4 5
2