Subgraphs

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


Submitting .cpp to 'Subgraphs'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 181
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 45
2 55
3 0