Travessia do gráfico. Componente de conectividade
Problem
Um grafo não direcionado não ponderado é dado. Para isso, você precisa encontrar o número de vértices que estão no mesmo componente conectado com um determinado vértice (contando este vértice).
Entrada: A primeira linha da entrada contém dois números: N e S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), onde N– o número de vértices do gráfico e S – top dado. As próximas N linhas contêm N números cada – matriz de adjacência do grafo, onde 0 significa nenhuma aresta entre os vértices e 1 – sua presença. É garantido que sempre haverá zeros na diagonal principal da matriz.
Resultado: Imprime um único número inteiro – número desejado de vértices.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3 1
0 1 1
1 0 0
1 0 0
| 3 |