Estruturas de Dados e Algoritmos 03/04

[22] Problema C - Redes de Circuitos Electrónicos


O problema

Um circuito electrónico consiste em diversos componentes, pontos de contacto (pins) e ligações (wires). A figura 1 mostra um circuito com 3 componentes: A, B e C. Cada ligação envolve um par de pontos de contacto.


Figura 1

Dois pontos de contacto a e b dizem-se electronicamente equivalentes se têm uma ligação directa entre eles, ou se se existe um sequência de pontos de contacto a1, a2, ..., ak, tal que existe ligação entre (a,a1), (a1,a2), ..., (ak, b). Uma rede é um conjunto máximo de pontos de contacto electronicamente equivalentes. Máximo é aqui usado no sentido de traduzir que nenhum ponto de contacto fora da rede é electronicamente equivalente a qualquer ponto dentro da rede.

Dado um conjunto de pontos de contacto e as suas respectivas ligações, a tua tarefa é descobrir o número de redes diferentes que existem no circuito. A figura 2 ilustra um circuito com 3 redes.


Figura 2

Input

Na primeira linha de input vem C, o número de casos a analisar.

De seguida, cada caso começa por duas linhas, a primeira das quais com um número N indicando o número de pontos de contacto existentes, seguido de uma outra linha com um número P, que indica o número de ligações existentes.

Por fim, vêm P linhas, cada uma com um par de números indicando que pontos de contacto estão conectados pela ligação. Os pontos de contacto são sempre identificados pelos números de 1 até N. Note que as ligações não vêm por nenhuma ordem em específico.

Vê o exemplo de input para perceberes melhor a especificação. (o primeiro caso de input corresponde à figura 2).

Output

Para cada caso deve ser imprimida uma única linha, contendo o número de redes do respectivo circuito.

Exemplo de input/output

Input Output
3
14
11
1 11
7 11
11 12
12 2
12 8
3 13
13 4
13 14
14 9
14 5
10 6
5
4
1 2
2 3
3 4
4 5
5
0
3
1
5

Última actualização: