Challenge: Count the Groups

Lab Python Intermediate 20 points

Places are connected by two-way roads. Print how many separate groups there are (places in a group can all reach each other; a place with no roads is a group by itself).

Input

Line 1: n m – the number of places (numbered 0 to n − 1) and the number of roads. Then m lines a b: a two-way road between a and b.

Output

The number of groups.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

Loop over every place; if it isn't seen yet, that's a new group.

From there, DFS or BFS to mark its whole group as seen.

Solution explanation

Every place and road is handled once: O(V + E).

Show solution

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
seen = [False] * n
groups = 0
for s in range(n):
    if not seen[s]:
        groups += 1
        seen[s] = True
        stack = [s]
        while stack:
            v = stack.pop()
            for w in g[v]:
                if not seen[w]:
                    seen[w] = True
                    stack.append(w)
print(groups)

Output

Answer