Problem Description
Given a graph of N nodes and E bidirectional edges, determine how many disjoint subgraphs there are in the graph. For this case, a portion of a graph is considered a subgraph if any 2 node in the portion are connected directly or indirectly. A node without any edges are also considered as a subgraph. Two disjoint subgraph will not have any edges in between any node of the first subgraph and any node of the second subgraph.
The nodes are labelled from 0 to N - 1 and there will not be 2 edges between any 2 pairs of nodes.
Input
2 integers, N then E
E lines consisting of 2 integers each, A and B. 0 ≤ A < B < N.
Output
A single integer, which is the number of disjoint subgraphs.
Limits
Subtask 1 (45%): N = 1000, 0 ≤ E ≤ 10000.
Subtask 2 (55%): N = 1000000, 0 ≤ E ≤ 1000000.
Subtask 3 (0%): As per sample testcases
Sample Testcase 1
Input:
5 3
1 2
3 4
4 0
Output:
2
Explanation:
The graph above contains 2 disjoint subgraphs: {1, 2} and {0, 3, 4}
Sample Testcase 2
Input:
5 4
0 1
1 2
2 3
3 4
Output:
1