Traversée de graphe. Composant de connectivité
Problem
Un graphe non orienté non pondéré est donné. Pour cela, vous devez trouver le nombre de sommets qui se trouvent dans le même composant connexe avec un sommet donné (en comptant ce sommet).
Entrée : La première ligne de l'entrée contient deux nombres : N et S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), où N&ndash ; le nombre de sommets du graphe, et S – sommet donné. Les N lignes suivantes contiennent N nombres chacune – matrice d'adjacence de graphe, où 0 signifie qu'il n'y a pas d'arête entre les sommets et 1 – sa présence. Il est garanti qu'il y a toujours des zéros sur la diagonale principale de la matrice.
Sortie : Imprime un seul entier &ndash ; nombre de sommets souhaité.
Exemples
| # |
Entrée |
Sortie |
| 1 |
3 1
0 1 1
1 0 0
1 0 0
| 3 |