#C9044. Kingdom Social Groups
Kingdom Social Groups
Kingdom Social Groups
In the Kingdom of Taco, citizens form social groups through friendships. Two citizens belong to the same social group if they are directly or indirectly connected via friendship relations. This can be modeled as an undirected graph where nodes represent citizens and an edge exists between two citizens if they are friends. Formally, if we denote the set of citizens as {1, 2, (\dots, N)} and friendship pairs as edges, the number of social groups is the number of connected components in the graph. Solve the problem by computing this number.
For example, if there are 4 citizens and 2 friendship pairs: (1, 2) and (3, 4), there are two social groups.
inputFormat
Input is provided via standard input (stdin). The first line contains two space-separated integers (N) and (M), where (N) is the number of citizens and (M) is the number of friendship pairs. The following (M) lines each contain two space-separated integers (A) and (B), indicating that citizen (A) is friends with citizen (B).
outputFormat
Output a single integer to standard output (stdout): the number of social groups in the kingdom.## sample
4 2
1 2
3 4
2